天天看点

comp3411 - week2 notes- Informed (Heuristic) Search

comp3411 - week2 notes- Informed (Heuristic) Search

给一个admissible的定义 ,如果对于所有的节点n,估计值h(n)都满足条件<= *(n)也就是实际的h(n), 那么f(n)也一定不会超过实际的成本。

comp3411 - week2 notes- Informed (Heuristic) Search

这里是对A算法最优的证明,就是说,如果h是admissible的,那么,A找到的状态,一定是全局最优,而不是局部最优的。

comp3411 - week2 notes- Informed (Heuristic) Search
comp3411 - week2 notes- Informed (Heuristic) Search

Iterative Deepening A* Search

迭代加深的a算法,结合了深度优先的算法,空间复杂度更低。

comp3411 - week2 notes- Informed (Heuristic) Search

如果是a,会先选A-E-G-k。

如果是ida*,会先选aehg,然后继续从g选,直到最优。选完之后,再和bdei比较,还可以继续选到aegk。

Constraint Satisfaction Problems

(CSPs)

n-Queens Puzzle as a CSP

comp3411 - week2 notes- Informed (Heuristic) Search

继续阅读