第四章状态空间搜索

第四章状态空间搜索内容摘要：

[ ] B [BA] [BCDA] [ ] E [EBA] [EFBCDA] [ ] H [HEBA] [HIEFBCDA] [ ] I [IEBA] [IEFBCDA] [H] F [FBA] [FBCDA] [EIH] J [JFBA] [JFBCDA] [EIH] C [CA] [CDA] [BFJEIH] G [GCA] [GCDA] [BFJEIH] 初值： SL=[A]； NSL=[A]； DE=[ ]； CS=A； 37 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 图搜索的实现  用未处理状态表 (NSL)使算法能返回 (回溯 )到其中任一个状态。  有一张 坏 状态表 (DE)避免算法重新搜索无解的路径。  有当前解题路径状态表 (SL),当满足目标时可以将它 〈 作为结果 〉 返回。  为避免陷入死循环必须是显式地对新状态进行检查, 看它是否在三张表中。 38 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring  Backtrack 是状态空间搜索的一个基本算法 ,后面所讲的图搜索算法 ,包括深度优先 ,广度优先 ,最好优先搜索 ,都有回溯中的思想。  基本思想是用表来保存搜索空间中状态轨迹的搜索算法。 39 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 度量问题求解的性能 完备性 最优性 时间复杂度 空间复杂度 当问题有解时，这个算法是否能够保证找到一个解 这个搜索策略是否能够找到最优解 找到一个解需要花费多长时间 在执行搜索的过程中需要多少内存 40 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和广度优先搜索 广度优先的基本思想： 从初始节点 S0开始逐层向下扩展，在第 n层节点还没有全部搜索完之前，不进入第 n+1层节点的搜索。 Open表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。 深度优先的基本思想： 从初始节点 S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。 41 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring J D C G F I H E B A 7 5 4 3 2 1 10 6 8 9 goal 深度和广度优先搜索 42 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 在深度优先搜索中，当查到某一个状态时，它所有的子状态以及子状态的后裔结点必须先于该状态的兄弟状态被查找。 尽量往深处走，只有再也找不出其后裔时才考虑兄弟。 广度优先搜索是一层一层地搜索空间，仅当某一层的状态全部搜索完毕，它才转入下一层搜索。 深度和广度优先搜索 43 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和广度优先搜索 图 用于广度及深度优先搜索的例图 A C F E G H I J D B U M L S K N O P R Q T 44 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和广度优先搜索 广度 优先搜索 关于实现： 为了保存状态空间搜索的轨迹 ,用到了 : open表和 closed表 open表：列出了已经产生出来但子状态未被查找的状态。 closed表：记录了已检查过的状态。 45 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring procedure breadth_first_search lnitialize:open=[start]。 closed=[ ]。 while open≠[ ] do begin 从 open表中删除最左边的状态 X。 if X 是目标 ,then 返回 (success)。 生成 X 所有的子状态。 将 X 放入 closed 表中。 从 X 的子状态中删除已经在 open或 closed表中的状态； 将其余子状态按生成的次序放入 open表的右边。 end 广度优先搜索 46 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring A C F E G H I J D B U M L S K N O P R Q T 目标状态 =[A]。 closed=[ ]。 =[B,C,D]。 closed=[A]。 =[C,D,E,F]。 closed=[B,A] =[D,E,F,G,H]。 closed=[C,B,A] =[E,F,G,H,I,J]。 closed=[D,C,B,A] =[F,G,H,I,J,K,L]。 closed=[E,D,C,B,A] =[G,H,I,J,K,L,M]。 closed=[F,E,D,C,B,A] =[H,I,J,K,L,M,N]。 closed=[G,F,E,D,C,B,A] 如此重复直到 U或 open=[ ] 47 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 是完备的 所需的时间和内存： 广度优先搜索 指数级复杂度 深度 节点数 时间 内存 2 1100 IMB 4 111， 100 11秒 106MB 6 107 19分钟 10GB 8 10931 小时 1TB 10 1011 129天 101TB 48 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和广度优先搜索  深度优先搜索 —— 如果已知解题路径很长 ,深度优先搜索就不会在图中大量的“浅层”状态上浪费时间。 —— 但深度优先搜索会在图的深处“迷失方向” ,找不到目标的更短路径或陷入到一个不通往目标的无限长的路径中。 —— 深度优先搜索耗费的空间量是路径长度值的线性函数。 —— 深度优先搜索不是最优的，不是完备的。 49 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 有界深度优先搜索 无边界的搜索树问题可以通过对深度优先搜索提供一个预先设定的深度限制来解决。 一旦搜索路径进入某一层时，深度限制便强迫该路径上的搜索失败。 解决了无穷路径问题。 又是造成不完备的原因。 深度优先搜索可以看作是有界深度优先搜索的一种特殊情况。 50 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例： 八数码问题。 在 3 3的方格棋盘上 ， 分别放置了表有数字 8的八张牌 ， 初始状态 S0， 目标状态 Sg，如下图所示。 可以使用的操作有： 空格左移 ， 空格上移 ， 空格右移 ， 空格下移 即只允许把位于空格左、上、右、下方的牌移入空格。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg •广度优先搜索策略 •深度优先搜索策略 51 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6。