Heuristic (informed) Search
Overview
- b: avg branching factor
- d: goal depth
- m: max depth
| Name | Space Complexity | Time Complexity | Complete | Optimal |
|---|---|---|---|---|
| Best-first search | O(bm), very bad | O(bm), very bad | No | No |
| A* Search | keep all generated nodes, bad | exponential, bad | Yes | Yes |
| Iterative‐deepening A* Search |
(Greedy) Best-first Search
- expansion based on evaluation function
f(n) - Evaluation function only consists of heuristic function h(n), i.e. f(n)= h(n). Allow backtrack.
- 參考影片: https://www.youtube.com/watch?v=WNuxP--PP2Y
A* Search
- Let g(n) be the cost we already took from initial state to n
- admissible heuristic: h(n)<=h*(n), where h* is the real minimum cost from n to Goal
- f(n) = g(n) + h(n)
- 參考影片: https://www.youtube.com/watch?v=-heqw27kllU&nohtml5=False
Iterative‐deepening A* Search
- Run A* with iteratively increasing cost limit
- Instead of depth, the limit is on the cost f(n)