Informed Search Flashcards
What is informed search?
A search algorithm that has a target goal state that it works towards
What is a search heurisitc?
A function that estimates how close a state is to a certain goal
What makes an admissible (optimistic) heuristic?
A heuristic h is admissible if:
0 <= h(n) <= h(n)
where h(n) is the true cost to a nearest goal
How does a best first-search work?
Use an evaluation function for each node and determine the most desirable unexpanded node.
What is the best-first search implementation?
Fringe is a queue sorted in decreasing order of desirability
How does a greedy search work?
It estimates the cost from n to the closest goal, and expands the node the appears to be closest to the goal. The nearest goal for each state
Is greedy search complete?
No, most often it will reach dead-ends/infinite loops.
What is the time complexity of greedy search?
O(b^m) good heuristics can give dramatic improvement.
What is the space complexity of greedy search?
O(b^m) all nodes are kept in memory
Is greedy search optimal?
No (best first take can often lead to the wrong goal)
What is the premise of A* search?
To avoid expanding paths that are already expensive.
What is the evaluation function of A* search?
f(n) = g(n) + h(n)
f(n) = estimated total cost of path through n to goal
h(n) = estimated cost to goal from n
g(n) = cost so far to reach n
Does A* search use and admissible heuristic?
Yes, it never overestimates the distance
Is A* search optimal?
Yes, it will find a solution and the cheapest one
Is A* search complete?
Yes, unless there are infinitely many nodes with f <= f(G)
