第三章状态空间搜索策略

第三章状态空间搜索策略内容摘要：

前面 ， 先进入的节点排在后面。 深度优先搜索 第三章 状态空间搜索策略 算法 状态空间图的深度优先搜索算法 (1)把初始节点 S0放人 OPEN表； (2)如果 OPEN表为空 ， 则问题无解 ， 退出； (3)从 OPEN表中将其第一个节点 (节点 n)移出 ， 放入已扩展节点表 CLOSED中； (4)考察节点 n是否为目标节点 ， 若是 ， 则找到问题的解 ，用 回溯法 求解的路径 ， 退出； (5)若节点 n不可扩展 ， 则转第 (2)步； (6)扩展节点 n ， 将 其后继节点放到 OPEN表的 前端 ， 并为其设置指向节点 n的指针 ， 然后转第 (2)步。 第三章 状态空间搜索策略 第三章 状态空间搜索策略 深度优先搜索 与 宽度优先搜索 的 区别 就在于：在对节点 n进行扩展时， 其后继节点在 OPEN表中的 存放位置。 宽度优先搜索 是将后继节点放入 OPEN表的 末端 ——“先入先出 ”。 深度优先搜索 是将后继节点放入 OPEN表的 前端 ——“后入先出 ”。 第三章 状态空间搜索策略 例 对例 ，利用深度优先方法进行搜索求解问题。 第三章 状态空间搜索策略 深度优先搜索的特点： 搜索策略是完备的。 搜索若进入某一分支，则沿着这一分支一直搜索下去，对于有限的状态空间图，从理论上讲，解总是能够找到的。 搜索效率低。 由于某些分支可能扩展得很深，而解又不在这些分支上，这就无疑会降低搜索的效率。 第三章 状态空间搜索策略 在深度优先搜索中，为了避免搜索过程沿着无穷的路径一直搜索下去，往往对一个节点扩展的最大深度进行限制。 任何节点如果达到了 深度界限 ，就把它作为没有后继节点进行处理，而对另一个分支进行搜索。 有界深度优先搜索 搜索树中 节点深度 (d)定义： (1)搜索树中 初始节点 的深度为 0。 (2)任何 其他节点 的深度等于其 父辈节点 的深度加上 1。 第三章 状态空间搜索策略 算法 有界深度优先搜索算法 (1)把初始节点 So放入 OPEN表中。 (2)如果 OPEN表为空，则问题无解，退出。 (3)把 OPEN表中的第一个节点 n从 OPEN表移到 CLOSED表。 (4)考察节点 n是否为目标节点，若是，则求得问题的解，退出；否则继续执行第 (5)步。 (5)如果节点 n的深度 dn等于最大深度 dm， 则转第 (2)步。 (6)如果节点 n不可扩展，即没有后继节点，则转第 (2)步；否则继续第 (7)步。 (7)扩展节点 n，将其后继节点放入 OPEN表的 前端 ，并为其设置指向节点的指针，转第 (2)步。 第三章 状态空间搜索策略 第三章 状态空间搜索策略 例 设八数码难题的初始状态及目标状态分别如下图 (a)和图 (b)所示，试用有界深度优先搜索策略求解问题。 深度界限 dm=5。 第三章 状态空间搜索策略 第三章 状态空间搜索策略 有界深度优先搜索算法的 深度界限的选择很重要。 选择过大，可能会影响搜索的效率；选择的过小，有可能求不到解。 有界深度优先 搜索策略是不完备的。 对于某些问题，可能它的解就位于某一分支较深的位置，而界限值选取的没有那么大，就会导致找不到问题的解。 第三章 状态空间搜索策略 搜索代价问题 ：在实际问题的搜索求解中，在将一个状态变换成另一个状态时，往往所付出的 操作代价 (或费用 )是不一样的，也就是状态空间图中各 有向边的代价 是不一样的。 这是前面讨论搜索算法没有考虑的。 代价树的宽度优先搜索 代价树 ：把 有向边 上标有 代价 的搜索树称为 代价搜索树 ，简称 代价树。 第三章 状态空间搜索策略 代价计算 ：在代价树中，把从初始节点 So到任意节点 i的路径代价记为 g(i)，而把从节点 i到其后继节点 j的连线之代价 (有向边代价 )记为 C(i,， j)，则 g(j)=g(i)+C(i， j)。 代价树宽度优先搜索的 基本思想 ：每次从 OPEN表中选择一个 代价最小 的节点，移入 CLOSED表。 第三章 状态空间搜索策略 算法 代价树的宽度优先搜索算法 (1)把初始节点 So放入 OPEN表，令 g(So)=0。 (2)如果 OPEN表为空，则问题无解，退出。 (3)把 OPEN表中 代价最小 的节点，即 排在前端的第一个节点 (即为节点n)，移入 CLOSED表中。 (4)如果节点 n是目标节点，则求得问题的解，退出，否则继续。 (5)判断节点 n是否可扩展，若不可扩展，则转 (2)步；否则转 (6)步。 (6)对节点 n进行扩展，将它们所有的后继节点放入 OPEN表中，并对每个 后继节点 j计算其代价 g(j)=g(i)+C(i， j)，为每个后继节点设置指向 n节点的指针，然后，根据节点的代价大小对 OPEN表中的 所有 节点进行从小到大的排序。 (7)转向第 (2)。