CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Heuristic search（启发式搜索）
- The idea is to develop a domain specific heuristic function h(n), guessing the cost of getting to the goal from node n
- We require that h(n) = 0 for every node n whose state satisfies the goal
- There are different ways of guessing this cost in different domains. i.e., heuristics are domain specfic.
Motivation
- In uninformed search, we don’t try to evaluate which of the nodes on the frontier are most promising.
- e.g., in uniform cost search we always expand the cheapest path. We don’t consider the cost of getting to the goal from the end of the current path.
- However, often we have some other knowledge about the merit of nodes.
- e.g., how costly it is to get to the goal from that node.
Greedy best-first search (Greedy BFS)
- We use $h(n)$ to order the nodes on the frontier.
- We are greedily trying to achieve a low cost solution.
- However, this method ignores the cost of getting to $n$, so it can be lead astray exploring nodes that cost a lot to get to but seem to be close to the goal
- Thus Greedy BFS is not optimal
A∗ search
- Define an evaluation function $f(n) = g(n) + h(n)$
- $g(n)$ is the cost of the path to node n
- $h(n)$ is the heuristic estimate of the cost of getting to a goal node from n
- So $f(n)$ is an estimate of the cost of getting to the goal via node n.
- We use $f(n)$ to order the nodes on the frontier
Conditions on h(n): Admissible
- We always assume that $c(n1 \to n2) ≥ \epsilon > 0$.The cost of any transition is greater than zero and can’t be arbitrarily small.
- Let $h∗(n)$ be the cost of an optimal path from n to a goal node ($\infty$ if there is no path).
- h(n) is admissible if for all nodes n, $h(n) \le h∗(n)$
- So an admissible heuristic underestimates the true cost to reach the goal from the current node
- Hence $h(g) = 0$ for any goal node $g$
Consistency (aka monotonicity)
- $h(n)$ is consistent/monotone if for any nodes $n_1$ and $n_2$, $h(n_1) \le c(n_1 \to n_2) + h(n_2)$
- Note that consistency implies admissibility (proof)
- no path from $n$ to the goal
- Let $n = n_1 \to n_2 \to \dots \to n_k$ be an optimal path from $n$ to a goal node. We prove by induction on i that for all i, $h(n_i) \le h∗(n_i)$.
- Most admissible heuristics are also monotone.
Time and space complexities
- When $h(n) = 0$, for all $n$, $h$ is monotone. A∗ becomes uniform-cost
- Hence the same bounds as uniform-cost apply. (These are worst case bounds). Still exponential unless we have a very good $h$!
Admissibility implies optimality
- Suppose that an optimal solution has cost C∗
- Any optimal solution will be expanded before any path with cost > C∗ (to be proved later)
- Note that in general, paths are not expanded in the order of their costs (see the example on Pg. 14)
- So the paths expanded before an optimal solution must have cost $\le$ C∗
- There are finitely many paths with cost $\le$ C∗
- Eventually we must examine an optimal solution, and a sub-optimal solution will not be examined before an optimal solution
Any optimal path will be expanded before any path of cost > C∗
Proof:
- Let p∗ be an optimal solution
- Assume that p is a path s.t. c(p) > c(p∗) and p is expanded before p∗
- Then there must be a node n on p∗ which is still in the frontier
- So $c(p) \le f(p) \le f(n) = g(n) + h(n) \le g(n) + h∗(n) = c(p∗)$, contradicting $c(p) > c(p∗)$
What about cycle checking
- We will show that monotonicity guarantees we have found an optimal path to a node the first time we visit it
- Thus with monotonicity, cycle checking preserves optimality
- However, with only admissibility, cycle checking might not preserve optimality.
- To fix this: for previously visited nodes, must remember cost of previous path. If new path is cheaper must explore again