- (S,F,G)表示一个问题的状态空间（S为初始状态集合，F为操作的集合，G为目标状态的集合）
- (S,F,G)可以使用状态空间图进行表示
- 求解：要么依据(S,F,G)穷举，要么在状态空间图找通路
设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。
猴子摘香蕉问题。在讨论知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。
思想
不断地分解和变换问题，将之转化为一系列较简单的子问题，通过求解子问题求解原问题。
- 分解：将一个问题分解为n个问题，若要解决原问题，这n个问题必须都得到解决
- 等价变换：将一个问题转换为n个问题，若要解决原问题，解决n个问题之一就可以
图形表示
求解
在构建的语义树中寻找可以推出原始问题的子树。
三阶梵塔问题。要求把1号钢针上的3个金片全部移到3号钢针上，如下图所示。
额外附送状态空间图
没有使用任何的启发式方式，盲目搜索
- Open表：存放未扩展的节点
- Closed表：存放已经扩展的节点
- S0：表示问题的初始状态
- Sg：表示问题的目标状态
搜索算法总过程
- 把初始节点S0放入Open表,设g（s0）=0, 建立一个CLOSED表，置为空；
- 检查Open表是否为空表，若为空，则问题无解，失败退出；
- 把Open表的第一个节点取出放入Closed表，并记该节点为n；
- 考察节点n是否为目标节点，若是则得到问题的解成功退出；
- 若节点n不可扩展，则转第（2）步；
- 下一步为扩展节点，依据不同的搜索策略进行扩展。
Breadth-first Search的第五步为：
- 扩展节点n， 将其子节点放入Open表的尾部，并为每个子节点设置指向父节点的指针, 转向第（2）步。
Open表可以认为是队列结构，先进入的先扩展。
- 完备的搜索策略，会得到路径最短的解
- 所占用的空间较大，若b为每个节点可以扩展的新节点，m为搜索树的层数，那么open表将会需要O(bm)的空间。
Depth-frist Search的第五步为：
- 扩展节点n， 将其子节点放入Open表的首部，并为每个子节点设置指向父节点的指针, 转向第（2）步。
Open表可以认为是栈结构，先进入的后扩展。
- 不完备的搜索策略，由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。
- 所占用的空间较小，若b为每个节点可以扩展的新节点，m为搜索树的层数，那么open表将会需要O(bm)的空间。
有界深度优先搜索方法
Iterative-deepening-depth-first_search
可以认为是广度优先搜索和深度优先搜索的结合体
可以扩展
Uniform-cost/Cheapest-first search的第五步：
- 扩展节点n， 生成子节点ni(i=1,2,……)，将其子节点放入Open表，并为每个子节点设置指向父节点的指针，计算各个节点的代价g(ni)，将Open表内的节点按g(ni)从小到大排序, 转向第（2）步。
Open表可以视为一个优先队列，将会先处理代价最小的未处理节点。
- 较深度和广度搜索可以添加代价，广度搜索可以认为是每条边代价相同的代价一致算法
hint：同一优先级，按字母顺序进行扩展
迭代次数 Open表 扩展节点 0 (S,0) 1 (A,1), (D,5) S 2 (B,4), (D,5) A 3 (C,5), (D,5), (G,5) B 4 (D,5), (G,5), (G,6) C 5 (G,5), (G,6), (G,6) D 6 (G,6), (G,6) G得到结果
值得注意的算法的执行过程
第五步如下：
- 扩展节点n， 生成子节点ni(i=1,2,……)，将其子节点放入Open表，并为每个子节点设置指向父节点的指针，依据启发式函数，将Open表内的节点按距离目标节点的距离从小到大排序, 转向第（2）步。
特点
- 搜索速度明显加快，但是找到的解可能不是最优解，
第五步如下：
- 扩展节点n， 生成子节点ni(i=1,2,……)，将其子节点放入Open表，并为每个子节点设置指向父节点的指针，依据启发式函数，将Open表内的节点按估价函数（从当前节点到目标节点的最优路径的估计代价+当前节点的实际代价）从小到大排序, 转向第（2）步。
该算法可以认为是贪心算法与代价一致算法的结合体。
- 启发函数一旦发生错误，将不会得到最优的解
A*算法对A算法的估价函数提出要求：
- 从当前节点到目标节点的最优路径的估计代价必须小于实际代价
- 可纳性，如果存在初始节点到目标节点的路径，A*算法总可以在有限步骤内找到最优路径
- 最优性，如果从当前节点到目标节点的最优路径的估计代价越接近真实代价，A*算法扩展节点数目越少（效率越高），且从当前节点到目标节点的最优路径的估计代价较低的A*算法扩展的节点一定包含较高A*算法扩展的节点。
- 单调限制性，如果启发函数满足以下两个条件: h(Sg )=0&&对任意节点ni 及其任一子节点nj ，都有0≤h(ni )-h(nj )≤c(ni , nj ) 其中c(ni , nj )是ni 到其子节点nj 的边代价，则称h(n)满足单调限制。
没看懂其中的单调限制性的问题
迭代次数 Open表 扩展节点 0 (S,0) 1 (B,2+1), (A,2+2) S 2 (A,2+2), (G,5+0) B 3 (G,4+0), (G,5+0) A 4 (G,5+0) G得到结果
估价函数为 f(n)=d(n)+W(n)
- W(n)表示节点n中“不在位”的数码个数。
- d(n)表示节点n在搜索树中的深度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/161337.html