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一個已經(jīng)被探測過得或者已經(jīng)存在在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.（如果我們的啟發(fā)方法是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
