Heuristic Function: Estimates the cost from a given state to the goal
Note: the goal test is performed when the node is popped from the frontier, NOT when it is generated during expansion.
A strategy is defined by picking the order of node expansion
Greedy search
Evaluation function f(n) = h(n) (entirely heuristic) = estimate of cost from n to the closest goal
Greedy search expands the node that appears to be closest to goal
Effect:
Complete: No–can get stuck in loops. Complete in finite space with repeated-state checking
Time: O(b^m), but a good heuristic can give dramatic improvement
Space: O(b^m)
Optimal: No
A∗ search
Idea: avoid expanding paths that are already expensive
Evaluation function f(n) = g(n) + h(n)
Admissible heuristic:
∀n h(n) ≤ h∗(n) where h∗(n) is the true cost from n.
When h(n) is admissible, f(n) never overestimates the total cost of the shortest path through n to the goal
Consistency: A∗ expands nodes in order of increasing f value
Theorem: if h is admissible, A∗ search finds the optimal solution
Effect:
Complete: Yes, unless there are infinitely many nodes with f ≤ C∗ Time: Exponential
Space: Exponential
Optimal: Yes—cannot expand fi+1 until fi is finished
Relaxed problems
Admissible heuristics can be derived from the optimal solution cost of a relaxed version of the problem
Key point: the optimal solution cost of a relaxed problem
is no greater than the optimal solution cost of the real problem
Graph search
不像tree search会有一个明确的detect方向,graph search 有2个set用于存放detected nodes, successors。
从successors set 里取一个node,当该node不是goal时就detect它的successor,如果没有被detected过且没有在successors set中,那么将其加入successors set,反之则抛弃。
When seeking optimal solutions, mutliple paths to the same state may need to be explored and compared to find the optimal。
这种情况下,我们就要detect一个已经被探测过得或者已经存在在successors set 中的node 是否存在一个更小的heuristic value,是则重新放入或者取代。
注意:If h is consistent (not just admissible), no re-opening is needed. h = 0 is consistent so no reopening is needed with uniform cost.(如果我们的启发方法是consistent,那么就不会有上一个问题了)
- For many problems, the state space is a graph rather than a tree.
- Cycles can prevent termination.
- Be exponentially more efficient than tree search.
- Often needed to ensure termination and optimality
- Stores all expanded nodes and requires extra tests