5. Informed Search 1 Flashcards
What is the main limitation of uninformed search?
It lacks guidance on how far a state is from the goal.
What is a heuristic function?
A function that estimates the cost of the cheapest path from a state to the goal.
What are the properties of a distance function?
Positivity, Symmetry, Identity, and Triangle Inequality.
Positive: d(x, y) >= 0,
Symmetrical: d(x, y) = d(y, x),
Identity: d(x, y) = 0 iff x = y,
Triangle Inequality: d(x, y) <= d(x, z) + d(y, z)
What are some common heuristic functions for path search problems?
Manhattan Distance, Euclidean Distance, Chebyshev Distance, and Unitary Distance.
What is the Manhattan distance formula?
h(n, g) = |n_x - g_x | + |n_y + g_y|
If h(n) = 0 and n = goal
What is the Euclidean distance formula?
h(n, g) = √((n_x - g_x)^2 + (n_y - g_y)^2)
What is the Chebyshev distance formula?
h(n, g) = max(|n_x - g_x | + |n_y + g_y|)
How is heuristic distance defined for the maze example?
As the physical distance (in meters) between chambers.
What are two heuristics for the 8-puzzle problem?
- Number of misplaced tiles, 2. Sum of Manhattan distances of each tile from its goal position.
What is Greedy Best-First Search?
A search algorithm that expands the node closest to the goal using a heuristic function.
What data structure does Greedy Best-First Search use?
A priority queue, where priority is determined by the heuristic function.
How does Greedy Best-First Search compare to Uniform-Cost Search?
Greedy Best-First Search selects the node with the lowest heuristic value, while Uniform-Cost Search selects the node with the lowest path cost.
What are the completeness and optimality properties of Greedy Best-First Search?
It is neither complete nor optimal.
What are the time and space complexities of Greedy Best-First Search?
Both are O(b^m), where b is the branching factor and m is the maximum depth.
What are the advantages of Greedy Best-First Search?
It optimizes time-to-goal by prioritizing seemingly closer nodes.
What are the disadvantages of Greedy Best-First Search?
It may get stuck in loops, follow costly non-optimal paths, or end up in dead-end branches.
What is the Unitary distance formula?
h(n ,g) = {{1 when n \neq g} {0 when n = g}}
