Informed Search

Question 1

What is an informed search?

Answer 1

search that uses domain-specific hints about the location of goals to find a solution more efficiently than uninformed searched

Question 2

What is a heuristic function?

Answer 2

h(n): the estimated cost of the cheapest path from the current node, n, to the goal state

Question 3

What is greedy best-first search?

Answer 3

an informed search algorithm

Form of best-first search where the node with the lowest h(n) is expanded first
- this node appears to be closest to the goal –> more likely to leave us to solution quickly

Question 4

What is the evaluation function of greedy best-first search? What is f(n)?

Answer 4

f(n) = h(n)

Question 5

Is greedy best-first search complete?

Answer 5

Yes, if there is a finite number of nodes

Question 6

What is the space complexity of greedy best-first search?

Answer 6

Worst case: O(b^m) where m = maximum depth of search space
Best case: O(bm)

Question 7

What is the time complexity of greedy best-first search?

Answer 7

Worst case: O(b^m) where m = maximum depth of search space
Best case: O(bm)

Question 8

What is A* search?

Answer 8

a best-first search algorithm where the cost of the current path plus the cost to move to the next node are taken into account. The cost function is… f(n) = g(n) + h(n)

Question 9

Is A* complete?

Answer 9

Yes, always returns shortest path

Returns no path if no path

Question 10

What is admissibility?

Answer 10

When an admissible heuristic never overestimates the cost of a path

Question 11

T/F: every consistent heuristic is admissible, and every admissible heuristic is consistent

Answer 11

False:
Every consistent heuristic is admissible
Not every admissible heuristic is consistent

Question 12

What is a contour?

Answer 12

a useful way to visualize a state space

Question 13

What does it mean to be monotonic?

Answer 13

When the cost always increases as you go along a path because action costs are always positive

the g cost increases like this in A*

Question 14

What does it mean to be optimally efficient?

Answer 14

When the most efficient solution will be the optimal one

Question 15

Why is A* efficient?

Answer 15

only looks at nodes in the search tree that contribute to the optimal solution

Question 16

What is an inadmissible heuristic?

Answer 16

A heuristic that may overestimate the cost to the goal state

Question 17

What is one downside of A*?

Answer 17

It expands a lot of nodes

Question 18

What is weighted A*?

Answer 18

Where the heiristic value is given more of a pull in the evaluation function

f(n) = g(n) + W * h(n), where W > 1

Question 19

What is the evaluation function of the following?

1. A* search
2. Uniform-cost search
3. Greedy best-first search
4. Weighted A* search

Answer 19

1. g(n) + h(n)
2. g(n)
3. h(n)
4. g(n) + W* h(n) , (1 < W < inf)

Question 20

What is a bounded suboptimal search?

Answer 20

when you look for the solution that is guaranteed to be within a constant factor W of the optimal cost

Question 21

What is a bounded-cost search?

Answer 21

when you look for a solution whose cost is less than some constant C

Question 22

What is an unbounded-cost search?

Answer 22

When you accept a solution of any cost, as long as it can be found quickly

Question 23

What is speedy search?

Answer 23

version of greedy best-first search where the heuristic estimates the number of actions required to reach a goal, not the cost of the actions

leads to high and low costs

Question 24

What is the main problem with A*?

Answer 24

Memory; keeps track of open and closed list

Question 25

What is a reference count?

Answer 25

tells the number of times a state has been reached and removed it from the closed list when there are no more ways to reach the state

e.g. in a grid world where each state can only be reached from its four neighbors, when a state is reached four times, it’s removed from the closed list

One way to decrease memory usage (i.e. A*)