Week 3 (Chapter 3) - Informed Search Methods Flashcards
What is “Best-first search”
Idea is to use an ‘evaluation function’ for each node to estimate the “desirability” of the particular node.
- Expand most desirable UNEXPANDED node
e. g. Greedy search
What is “Greedy search”
Greedy search expands the node that appears to be closest to goal. Only considers the most immediate depth.
Evaluation function h(n)
(heuristic) = estimate cost from n to goal
What are the properties of “Greedy search”
Complete - No, can get stuck in loops. If in finite space with repeated-state checking, it can be complete.
Time - O(b^m), but a good heuristic can have dramatic impact
Space - O(b^m), keeps all nodes in memory
Optimal - No
b = maximum branching factor of the search tree m = maximum depth of the state space (may be infinite)
What is “A* search”
Idea is to avoid expanding paths that are already expensive
Evaluation function f(n) = g(n) + h(n)
g(n) = cost so far to reach n (path cost) h(n) = estimated cost to goal from n f(n) = estimated total cost of path through n to goal
A* search uses an admissible heuristic
i.e., h(n) <= h(n) where h(n) is the true cost from n
- Never overestimates the actual road distance
- Therefore A* search is optimal
Give proof that A* is optimal
Suppose some suboptimal goal G2 has been generated and is in the queue. Let n be an unexpanded node on a shortest path to an optimal goal G.
f(G2) = g(G2) since h(G2) = 0
____> g(G) since G2 is suboptimal
____≥ f(n) since h is admissible
Since f(G2) > f(n), A∗ will never select G2 for expansion
A* expands nodes in order of increasing f value
What are the properties of A* search
Complete - Yes, unless there are infinitely many nodes with f <= f(g)
Time - Exponential
Space - O(b^d) Keeps all nodes in memory
Optimal - Yes
b = maximum branching factor of the search tree d = depth of the least-cost solution m = maximum depth of the state space
Because A* search is optimal, it doesn’t go down m depths deep
What are “Heuristics”
Think of them as evaluation functions to be used at each node to better inform the search tree of the optimal path to take
e. g. for the 8-puzzle;
- Number of misplaced tiles
- Total Manhattan distance (# of squares from desired location of each tile)
Elaborate on “Dominance” for heuristics
If h1(n) >= h2(n) for all n, then h1 DOMINATES h2 and is better for search
- Do this because we don’t want a heuristic which can be too expensive to compute at each node
What are “Relaxed problems”?
How to approach deriving an admissible heuristic.
What are “Iterative improvement algorithms?”
In many optimisation problems, path is irrelevant; the goal state itself is the solution
- This is very costly
Alternatively, we can do this iteratively by keeping a single “current” state, and try to improve it
Thus, we can solve this with CONSTANT SPACE
e.g. Traveling salesperson or n-queens
What is “Hill-climbing”
Iteratively search until a maxima is found, however, can get stuck in local maxima depending on the initial state
What’s an example of “Best-first search”
Greedy search
