6. Informed Search 2 Flashcards
What is A* Search?
A search algorithm that expands nodes based on the sum of the path cost and the heuristic estimate .
What is the function used in A* Search to determine node expansion?
f(n) - min_c[g(n) + h(c)], where g(n) is the path cost and h(n) is the heuristic cost to the goal.
What data structure does A* Search use?
A priority queue, where priority is determined by p(n) = g(n) + h(n).
How does A* Search compare to Uniform-Cost Search (UCS)?
A* Search considers both path cost and heuristic cost, whereas UCS considers only path cost.
What makes A* Search complete?
It is complete if the lowest cost is greater than or equal to zero.
Under what condition is A* Search optimal?
A* is optimal if the heuristic is admissible and consistent.
What is an admissible heuristic?
A heuristic that never overestimates the actual cost to the goal: 0 <= h(n) <= h*(n).
Give examples of admissible heuristics.
Manhattan distance, Euclidean distance, and Chebyshev distance.
What is a consistent heuristic?
A heuristic where for every node (n) and successor (n’) are generated by an action (a), the estimates cost of reaching the goal from n is no greater than the step cost of getting n’ + the estimated cost of reaching the goal from n’: h(n) <= c(n, a, n’) + h(n’).
What is heuristic dominance?
Given two admissible heuristics, h_1(n) and h_2(n). If h_2(n) >= h_1(n) for all nodes n, then h_2 dominates h_1 and results in fewer node expansions.
How does heuristic dominance improve efficiency?
A more dominant heuristic results in fewer expanded nodes, making A* more efficient.
What are two heuristics used for the 8-puzzle problem?
- Number of misplaced tiles, 2. Sum of Manhattan distances of each tile from its goal position.
What are some variations of A* Search?
Iterative Deepening A* (IDA), Memory-bound A (MA), Simplified Memory-bound A (SMA), D algorithm, and Rapidly-exploring Random Tree (RRT).
What are the time and space complexities of A* Search?
Both are O(b^m), where b is the branching factor and m is the maximum depth.
What is the biggest drawback of A* Search?
It requires high memory space due to storing all generated nodes.
