文章目录
- 一、状态空间图
- 二、搜索方法
一、状态空间图
(深度优先)
1.状态空间图不一定总能画出来,只有两个要素:状态、连接
2.建立状态空间图,需要:
– 定义状态形式
– 定义状态之间的连接的意义
– 定义问题的解的形式(状态解、路线解、最优值解等)
实例:
二、搜索方法
1.盲目/通用搜索
主要指:深度优先搜索、宽度优先搜索
2.贪心搜索
贪婪搜索策略:总是做出在当前看来最好的选择,或者采用使得当前步骤获利最大的选择,因此也叫做贪婪算法。
– 贪婪搜索策略不考虑整体最优,仅求取局部最优。因而也可以看作是一种“盲目”的策略。
– 贪婪搜索不能保证得到最优解,但搜索速度非常块。
– 对一些特定问题很有效。
总结:
深度、宽度优先搜索通用性强,但效率慢
贪婪搜索速度非常块,但基本上找不“准”
3.启发式搜索
3.1 A算法
3.2 A算法*