本文共 442 字，大约阅读时间需要 1 分钟。

一、状态空间图

（深度优先）

1.状态空间图不一定总能画出来，只有两个要素：状态、连接 2.建立状态空间图，需要： – 定义状态形式 – 定义状态之间的连接的意义 – 定义问题的解的形式（状态解、路线解、最优值解等） 实例：

二、搜索方法

1.盲目/通用搜索

主要指：深度优先搜索、宽度优先搜索 2.贪心搜索

贪婪搜索策略：总是做出在当前看来最好的选择，或者采用使得当前步骤获利最大的选择，因此也叫做贪婪算法。

– 贪婪搜索策略不考虑整体最优，仅求取局部最优。因而也可以看作是一种“盲目”的策略。 – 贪婪搜索不能保证得到最优解，但搜索速度非常块。 – 对一些特定问题很有效。

总结：

深度、宽度优先搜索通用性强，但效率慢 贪婪搜索速度非常块，但基本上找不“准”

3.启发式搜索

3.1 A算法 3.2 A算法*

4.博弈搜索

4.1 极大极小博弈 我得分最多就是你得分最少 4.2 固定深度博弈 注意：宽度优先 考虑若干步的极大极小博弈

4.3 α-β剪枝

注意：深度优先

转载地址：http://hyxki.baihongyu.com/