Informed Search Flashcards
What is cost cost-sensitive search?
Similar to BFS, but sorts the queue using the path cost. Unfortunately, this search explores in every “direction.”
What is a heuristic?
A function that estimates how close a state is to a goal.
Designed for a particular search problem
A rule of thumb that helps decide which is the most promising path to take during search.
In search, heuristic should be an underestimate of actual cost to get from current node to any goal.
What is an informed search strategy?
One that uses problem-specific knowledge beyond the definition of the problem itself
One can find solutions more efficiently than an uninformed strategy.
Often implemented using a priority queue to store frontier nodes.
What is greedy (best-first) search?
This search selects the node for expansion using the heuristic function for its evaluation function. Greedy search minimises the estimated cost to the goal, it expands whichever node n is estimated to be closest to the goal.
What are the properties of greedy best-first search?
Completeness - guaranteed, if b is finite and with repeated state-checking
Admissibility - not guaranteed
Space - O(b^m)
Time - O(b^m)
Optimal - no
What is A* search?
Uses both the cost of path generated and estimated to goal to order nodes on the frontier.
f(n) = g(n) + h(n)
g(n) - cost from initial node to node n
f(n) - estimated total cost of cheapest solution through node n
f(n) is the estimated cost of the cheapest solution extending this path
What are the properties of A* search?
Completeness - guaranteed
Admissibility - guaranteed is heuristic is admissible/consistent
Space- O(b^d)
Time - O(b^d)
Optimal - yes
What is admissiblility?
An admissible heuristic is one that never overestimates the cost to reach the goal. Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.
What is consistency?
A heuristic is consistent if for every node n, if the summed path cost is less than the straight cost to get to the same node.
What is Euclidean distance?
sqrt((x2-x1)^2 + (y2-y1)^2)
What is Manhattan distance?
|x1 - x2| + |y1 - y2|
What is iterative deepening A* search?
A low memory variant of A* which performs a series of depth-first searches bu cuts off each search when the sum f(n) exceeds some predefined threshold.
What is dominance?
If one heuristic is better than another, it is a dominant hueristic
What are the properties of A* search?
Completeness - guaranteed
Admissibility - guaranteed if heuristic is admissible/consistent
Space - O(bd)
Time - O(b^d)
Optimal - yes (assuming h(n) is admissible)
What is the difference between A* search and iterative deepening A*?
Memory wise, IDA* is better for memory, worse for time
A* uses a priority queue, IDA* uses a stack
A* uses open and closed lists, but IDA* doesn’t use either.
