comp3411 – week2 notes- Informed (Heuristic) Search

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

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

Iterative Deepening A* Search

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

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

Constraint Satisfaction Problems

(CSPs)

n-Queens Puzzle as a CSP

每列一个皇后,皇后的位置是变量Qi, 定义域是1,2,3,4从上数的第几行。问怎么样才能不会被吃。

【转自:美国cn2服务器 mg.html欢迎留下您的宝贵建议】都属于昨天。哪怕那山再青,那水再秀,

comp3411 – week2 notes- Informed (Heuristic) Search

相关文章:

你感兴趣的文章:

标签云: