Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Y1S2_IT1244 > CHAP 4 : Search techniques (informed) > Flashcards

CHAP 4 : Search techniques (informed) Flashcards

1
Q

** What is true for informed search?

  1. Can distinguish goal states from non-goal states.
  2. Can tell which non-goal state is better, given some guidance.
  3. Cannot tell which non-goal state is better
  4. Uses an evaluation function that controls the path of the search.
A

1,2,4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the idea behind Best-first search?

A
  • Use an evaluation function, f(n) for each node. It gives an estimate of desirability and we expand the most desirable unexpandable nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How to implement best first search? (what data structure is used)

A
  • Order the nodes in frontier in decreasing order of desirability with priority queue data structure.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the 2 special cases of best first search?

A
  1. Greedy best-first search
  2. A* Seach
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the aim of greedy best first search and its drawback?

A

It aims to minimise search cost , h(n) to the destination by reducing the search domain considerably

Drawback : result is suboptimal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does greedy best first search compute the cheapest cost to the goal state?

A

Through heuristic function, h(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Best first search uses an evaluation function for specific nodes only. Is the statement true or false?

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Evaluation function can be described as an estimate of “desirability” to reach goal state. Is the statement true or false?

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

** The implementation of Best-first search orders the nodes in the frontier only in increasing order of desirability. Is the statement true or false?

A

False, in decreasing order of desirability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Greedy best-first search expands the node that is truly-closest to the goal. Is the statement true or false?

A

False. It expands the node that appears to be closest to the goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Evaluate the Greedy Best-first search algorithm. (Completeness, optimal, time and space)

A

Completeness : Yes, if state space is finite and no duplicate nodes are expanded.

Optimal : No.

Time and space : time and space complexities are exponential if bad heuristic function is used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Greedy best-first search with a good heuristic function is usually:

  1. Complete
  2. Optimal
  3. Time-efficient
  4. Space-efficient
A

1,3,4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the aim of uniform cost search and its drawback?

A

It minimises the cost of the path, g(n) and finds the optimal solution

Drawback : inefficient when domain is large

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What kind of function does A* Search use to compute the estimated total cost of the cheapest solution through the current node?

A

Evaluation function, f(n)

f(n) = g(n) + h(n)

g(n) = actual cost to current state
h(n) = estimated cost to reach goal from current state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

A* search takes advantage of both Greedy Best-first Search and Uniform Cost search. Is the statement true or false?

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A* search is most popularly used in games. Is the statement true or false?

A

True

17
Q

What are the 2 criteria that the heuristic function must possess?

A
  1. Admissible
  2. Consistent
18
Q

What is meant by an admissible heuristic function?

A

A heuristic function is admissable if for every node n, h(n) <= h*(n)

h*(n) : TRUE COST to reach goal state from current node n

It means that the heuristic function never overestimates the cost to reach the goal.

19
Q

What is meant by a consistent heuristic function?

A

A heuristic is consistent if for every node n, every successor n’ of n generated by any action a , we have h(n) <= c(n,a,n’) + h(n’), where c(n,a,n’) is the estimated step cost from n to n’

— basically, a consistent heuristic will not discard truly good options just because it overestimates their cost and treat them as bad options.

20
Q

Evaluate the A* search algorithm

A

Complete : Yes, if there is finite no of nodes with cost less than or equal to the cost of the optimal solution path.

Optimal : Yes, if h(n) is consistent

Time and space : Bad in time and space complexity. The space + amt of time is not small, for a big state space, the tree built is very big while enlarging the frontier

Runs out of space before running out of time.

21
Q

What is optimaisation in AI?

A

The process to find the state at which the objective function is minimum or maximum.

22
Q

Local search deals with problems where the path to the goal is irrelevant, and its only aim is to find the goal state. Is the statement true or false?

A

True

23
Q

Benefits of local search? [3]

A
  1. Checks and updates only the curent state along the path
  2. Require very little/constant memory
  3. Find reasonable solutions in large / infinite state spaces
24
Q

How is local search conducted? [4 steps]

A
  1. Start with a feasible solution x
  2. Define a neighbourhood of x
  3. Identify an improved neighbour y
  4. Replace x by y and repeat
25
Q

What is hill-climbing algorithm?

A

A hill-climbing algorithm is a local search algorithm that moves continuously upward (increasing) / DOWNWARD (decreasing) until the best solution is attained.

26
Q

What is an objective function?

A

The real-valued function whose value is to be either minimized or maximized subject to the constraints.

27
Q

What are the axes for hill-climbing algorithm?

A

y-axis : objective function
x- axis : state space

28
Q

What are the drawbacks of hill-climbing algorithm? [2]

A
  1. It cannot detect whether it’s in a local minimum/maximum or a global minimum/maximum.
  2. It is not always possible to find a global maximum using a hill-climbing search, as there might be local maxima that the algorithm can stuck at.
29
Q

For the map colouring problem, the either of the followings can be the objective function for optimization. True or False?

(a) number of conflicting regions

(b) number of non-conflicting regions

A

True.

Aim : minimise no of conflicting regions / maximise no of non-conflicting regions

Y1S2_IT1244 (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions