1、第五章 搜索技术第五章 搜索技术0101图搜索策略图搜索策略0202盲目搜索盲目搜索0303启发式搜索启发式搜索0404博弈搜索博弈搜索第五章 搜索技术0101图搜索策略图搜索策略0202盲目搜索盲目搜索0303启发式搜索启发式搜索0404博弈搜索博弈搜索第五章 搜索技术如何求解问题？如何求解问题？1、明晰问题如何表示、明晰问题如何表示2、选择相对合适的求解方、选择相对合适的求解方法法搜索法、归纳法、归结法、推理法、产生式、etc搜索法第五章 搜索技术搜索中需要解决的基本问题：搜索中需要解决的基本问题：01020304找到的解找到的解是否是最是否是最佳解佳解是否会终是否会终止 运 行止 运 行
2、 / /陷入一个陷入一个死循环死循环是否一定是否一定能找到一能找到一个解个解时间与空时间与空间复杂性间复杂性如何如何搜索过程：搜索过程：当前状态当前状态扫描算子集扫描算子集建立新状态建立新状态建立指针建立指针是否是否满足满足? ?给出解给出解答路径答路径NY第五章 搜索技术6 (1) 数据驱动：从初始状态（数据驱动：从初始状态（问题给出的条件）问题给出的条件）出发的正向搜索出发的正向搜索 (2) 目的驱动：从目的目的驱动：从目的状态出发的逆向搜索状态出发的逆向搜索从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的
3、某处汇合为止。索，直到两条路径在中间的某处汇合为止。(3) 双向搜索双向搜索搜索策略（按方向）搜索策略（按方向）第五章 搜索技术搜索策略（按信息运用度搜索策略（按信息运用度）（1）盲目搜索：）盲目搜索：在不具有对特定问题的任何有关信息的在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。搜索。 （2）启发式搜索：）启发式搜索：考虑特定问题领域可应用的知识，动考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少
4、不必要的搜索，以求尽快地到达结束状态。尽量减少不必要的搜索，以求尽快地到达结束状态。第五章 搜索技术8 状态状态：表示系统状态、事实等叙述型知识的一组变量或数组：表示系统状态、事实等叙述型知识的一组变量或数组：,21mfffF 操作：操作：表示引起状态变化的过程型知识的一组关系或函数：表示引起状态变化的过程型知识的一组关系或函数：,21nqqqQT图搜索策略图搜索策略状态空间：状态空间：利用状态变量和操作符号，表示系统或问题的有利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：关知识的符号体系，状态空间是一个四元组：),(0GSOS状态集合状态集合 操作算子的集
5、合操作算子的集合若干具体状态或满足某若干具体状态或满足某些性质的路径信息描述些性质的路径信息描述包含问题的初始状态是包含问题的初始状态是 的非空子集的非空子集S第五章 搜索技术9 求解路径求解路径：从 结点到 结点的路径。 0SGGSSSkOOOO321210kOO,1：状态空间的一个解：状态空间的一个解 状态空间的一个解状态空间的一个解：一个有限的操作算子序列。图搜索策略图搜索策略第五章 搜索技术10 例例5.1 八数码问题的状态空间八数码问题的状态空间。 状态集状态集 ：所有摆法：所有摆法S操作算子：操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right图
6、搜索策略图搜索策略第五章 搜索技术11八数码八数码状态空间图状态空间图 图搜索策略图搜索策略第五章 搜索技术12（状态）（操作算子）状态空间的有向图描述状态空间的有向图描述图搜索策略图搜索策略第五章 搜索技术13 例例5.2 旅行商问题旅行商问题（traveling salesman problem, TSP）或邮递员路径问题。或邮递员路径问题。 （家）（单位：km）可能路径：可能路径：费用为费用为375的路径的路径（A，B，C，D，E，A） 图搜索策略图搜索策略第五章 搜索技术14 旅行推销员状态空间图（部分）旅行推销员状态空间图（部分） ABCDEA 375 A A A A B B C C
7、 C C D D D D A E E E E E E E D 路径路径: 路径: 路径 : 路径: ABCEDA ABDCE ABDECA 费用 : 费用 : 费用 : 费用: 425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 图搜索策略图搜索策略第五章 搜索技术0202盲目搜索盲目搜索0101图搜索策略图搜索策略0303启发式搜索启发式搜索0404博弈搜索博弈搜索第五章 搜索技术16U U 1. 回溯策略回溯策略UU
8、2. 宽度优先搜索策略宽度优先搜索策略UU 3. 深度优先搜索策略深度优先搜索策略盲目搜索盲目搜索第五章 搜索技术17 带回溯策略的搜索带回溯策略的搜索： 从初始状态出发，不停地、试探性地寻找路径，直到它到达到达目的目的或“不可解结点不可解结点”，即“死胡同”为止。 若它遇到不可解结点不可解结点就回溯回溯到路径中最近的父结点父结点上，查看该结点是否还有其他的子结点子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。盲目搜索（回溯策略）盲目搜索（回溯策略）第五章 搜索技术181 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意图回溯搜
9、索示意图盲目搜索（回溯策略）盲目搜索（回溯策略）第五章 搜索技术19回溯搜索的算法回溯搜索的算法(1) PS（path states）表）表：保存当前搜索路径上的状态保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。 (2) NPS（new path states）表）表：新的路径状态表新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展 。(3) NSS（no solvable states）表）表：不可解状态集，列出了不可解状态集，列出了找不到解题路径的状态找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状
10、态继续搜索。 盲目搜索（回溯策略）盲目搜索（回溯策略）第五章 搜索技术20图搜索算法的回溯思想：图搜索算法的回溯思想：（1）用未处理状态表（未处理状态表（NPS）使算法能返回（回溯）到其 中任一状态。 （2）用一张“死胡同死胡同”状态表（状态表（NSS）来避免算法重新搜索 无解的路径。 （3）在PS 表表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回。 （4）为避免陷入死循环必须对新生成的子状态进行检查对新生成的子状态进行检查， 看它是否在该三张表中 。盲目搜索（回溯策略）盲目搜索（回溯策略）第五章 搜索技术21FFopen表（表（NPS表）表）： 已经生成出来但其子状态未被搜索
11、的状态。FFclosed表表（PS表和表和NSS表的合并）表的合并）： 记录了已被生成扩展过的状态。 0S12345678910宽度优先搜索法中状态的搜索次序宽度优先搜索法中状态的搜索次序盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）第五章 搜索技术22 例例5.3 通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。 BCAABC(a) 初始状态(b) 目的状态 积木问题积木问题盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）第五章 搜索技术23 操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。MOVE（A，Table）：）：“搬动积木搬动积木A到桌到桌面
12、上面上”。 操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。（2）如果 Y 是积木，则积木 Y 的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）第五章 搜索技术24ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(A,TABLE)MOVE(C,A)MOVE(C,A)MOVE(A,C)MOVE(A,C)MOVE(B,A)MOVE(B,A)MOVE(B,C)MOVE(B,C) MOVE(C,A) MOVE(C,A)MOVE(C,B)MOVE(C,B) MOVE(C,B)
13、 MOVE(C,B)MOVE(A,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，没有后裔，失败退出失败退出积木问题的宽度优先搜索树积木问题的宽度优先搜索树盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）BCAABC第五章 搜索技术250S12345678910111213KK 深度优先搜索法中状态的搜索次序深度优先搜索法中状态的搜索次序0S12345678910111213KK盲目搜索（深度优先策略）盲目搜索（深度优先策略）第五章 搜索技术26Q Q 在深度优先搜索中，当搜索到某一个状态时，它在深度优先搜索中，当搜索到某一个状态时，它所有的子状所有的子状态以及子
14、状态的后裔状态都必须先于该状态的兄弟状态态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。被搜索。 Q Q 为了保证找到解，应为了保证找到解，应选择合适的深度限制值选择合适的深度限制值，或采取不断加，或采取不断加大深度限制值的办法，反复搜索，直到找到解。大深度限制值的办法，反复搜索，直到找到解。 盲目搜索（深度优先策略）盲目搜索（深度优先策略）Q Q 深度优先搜索深度优先搜索并不能保证第一次并不能保证第一次搜索到的某个状态时的路径搜索到的某个状态时的路径是是到这个状态的到这个状态的最短路径最短路径。 Q Q 对任何状态而言，以后的搜索有可能找到另一条通向它的路对任何状态而言，以后的搜索有
15、可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它个状态时，它应该保留最短路径应该保留最短路径。 第五章 搜索技术27 例例5.4 卒子穿阵问题卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退。假定深度限制值为5。 000100100100000121342134行列图 5.10阵 列 图000100100100000121342134行列图 5.10阵 列 图 阵列图阵列图 盲目搜索（深度优先策略）盲目搜索（深度优先策略）第五
16、章 搜索技术28, ,解解死死死死死死深度限制深度限制解S0S1(1,1)S2(1,2)S3(2,2)S4(2,1)S5(3,1)S6(3,2)S7(2,3)S8(2,1)S9(3,1)S10(1,3)S18(1,4)S11(1,2)S14(1,4)S12(2,2)S15(2,4)S13(2,3)S16(3,4)S17(4,4)open表：S17、S18closed表：S0S16 卒子穿阵的深度优先搜索树第五章 搜索技术0101图搜索策略图搜索策略0202盲目搜索盲目搜索0303启发式搜索启发式搜索0404博弈搜索博弈搜索第五章 搜索技术30N N “启发启发”（heuristic）：关于发现
17、发现和发明发明操作算子操作算子及搜搜索方法索方法的研究研究。三、启发式搜索三、启发式搜索 启发式策略：启发式策略：利用利用与问题有关的启发信息启发信息进行搜索搜索。O O 启发式启发式: 在状态空间搜索中，启发式启发式被定义成一系列操作操作算子算子，并能从状态空间中选择选择最有希望到达问题解的路径路径。第五章 搜索技术31 （1）一个问题由于在问题陈述和数据获取方面固有的模糊性，模糊性，导致它没有一个确定的解导致它没有一个确定的解。三、启发式搜索三、启发式搜索（2）虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。适用范围：适用范围：局限性：局
18、限性： 启发（猜想猜想）根据经验和直觉判断，可能得到的是次优解，可能得到的是次优解，也可能一无所获也可能一无所获。第五章 搜索技术32 例例5.5 5.5 一字棋。在九宫棋盘上，从空棋盘开始，双方轮流一字棋。在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上摆各自的棋子在棋盘上摆各自的棋子或或（每次一枚），谁先取得三子（每次一枚），谁先取得三子一线（一行、一列或一条对角线）的结果就取胜。一线（一行、一列或一条对角线）的结果就取胜。 和 在棋盘中不同位置对应的棋局就是问题空间中的不同状态。 9个位置上摆放空，空， ， 有 39 种棋局。 可能的走法 ： 。1789三、启发式搜索三、启发式搜索 第五章
19、搜索技术33三、启发式搜索三、启发式搜索O赢的概率：赢的概率：8-5=3O赢的概率：赢的概率：8-6=2O赢的概率：赢的概率：8-4=4一字棋：9！，西洋跳棋：1078，国际象棋：10120，围棋：10761。假设每步可以搜索一个棋局，用极限并行速度（10-104年/步）来处理，搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完！ 第五章 搜索技术34图5.13启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间三、启发式搜索三、启发式搜索最佳走步最佳走步第五章 搜索技术35更准确精炼描述状态更准确精炼描述状态启发信息分类陈述性过程性用于构造操作算子少而精用
20、于构造操作算子少而精表示控制策略知识表示控制策略知识控制性没有任何控制性知识作为搜索的依据，没有任何控制性知识作为搜索的依据，搜索是随意的搜索是随意的有充分的控制知识作为依据，因而搜索的每有充分的控制知识作为依据，因而搜索的每一步选择都是正确的，但这一步选择都是正确的，但这是不现实的是不现实的第五章 搜索技术36 评估函数评估函数：估计待搜索结点的“有希望”程度，并依次给它们排定次序（在open表中）。 ：从初始结点经过初始结点经过 结点到达目的结点结点到达目的结点的路径的最小代最小代 价估计值价估计值)(nfn)()()(nhngnf 一般地，在一般地，在 中，中， 的比重越大，越倾向于宽度
21、优的比重越大，越倾向于宽度优先搜索方式，而先搜索方式，而 的比重越大，表示启发性能越强。的比重越大，表示启发性能越强。( )f n( )g n( )h n三、启发式搜索三、启发式搜索 ：从初始结点到初始结点到 结点结点的实际代价实际代价估计值)( g nn ：从 结点到目的结点结点到目的结点的最佳路径最佳路径估计代价值估计代价值n)( h n第五章 搜索技术37 open表：保留所有已生成而未扩展的状态。 closed表：记录已扩展过的状态。 进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展。 三、启发式搜索三、启发式搜索设计评估函
22、数的目标：设计评估函数的目标： 利用有限的信息作出一个较精确的评估函数利用有限的信息作出一个较精确的评估函数启发式图搜索法的基本特点：启发式图搜索法的基本特点：寻找并设计一个与问题有关的 及构出 ，然后以 的大小来排列待扩展状态的次序，每次选择 值最小者进行扩展。)(nh)()()(nhngnf)(nf)(nf第五章 搜索技术 A算法（基于评估函数的算法（基于评估函数的加权启发式图搜索算法加权启发式图搜索算法）实现步骤实现步骤2 2、若、若open表为空，则搜索失败，退出表为空，则搜索失败，退出3 3、移出、移出openopen表中第一个节点表中第一个节点N N放入放入closed表中，并顺序
23、编号表中，并顺序编号n n4 4、若目标结点把附有、若目标结点把附有 的初始的初始 , ,则搜索成功，结束则搜索成功，结束5 5、若、若N N不可扩展，则转步骤不可扩展，则转步骤2 26 6、扩展、扩展N N，生成一组附有，生成一组附有 的子结点，对这组子结点进行处的子结点，对这组子结点进行处理：理： 考察是否有已在考察是否有已在open或或closed表中存在的结点。若有则再考察表中存在的结点。若有则再考察其中有无其中有无N N的先辈结点，有则删除，同时考虑是否修改表中结点的先辈结点，有则删除，同时考虑是否修改表中结点及其后裔指针和及其后裔指针和 的值的值 为其余子结点配上指向为其余子结点配
24、上指向N N的返回指针后放入的返回指针后放入open表中，并排序，表中，并排序，转步骤转步骤2 2 0sf1 1、把附有、把附有 放入放入openopen表表0sfNgS xf xf第五章 搜索技术39 A算法描述算法描述procedure heuristic_searchopen：=start；closed：= ；f(s)：=g(s)+h(s)；*初始化while open dobegin从open表中删除第一个状态，称之为n；if n=目的状态then return(success)；生成n的所有子状态；if n没有任何子状态then continue；for n的每个子状态docase子
25、状态is not already on open表or closed表；begin计算该子状态的估价函数值；将该子状态加到open表中； end； 第五章 搜索技术40case子状态is already on open表：if该子状态是沿着一条比在open表已有的更短路径而到达then 记录更短路径走向及其估价函数值；case子状态is already on closed表：if该子状态是沿着一条比在closed表已有的更短路径而到达thenbegin将该子状态从closed表移到open表中；记录更短路径走向及其估价函数值；end；case end；将n放入closed表中；根据估价函数值，
26、从小到大重新排列open表；end；*open表中结点已耗尽return(failure)；end.第五章 搜索技术41 每次重复时，每次重复时，A搜索算法从搜索算法从open表中取出第一个状态，如果表中取出第一个状态，如果该状态满足目的条件，则算法返回到该状态的搜索路径。该状态满足目的条件，则算法返回到该状态的搜索路径。 如果如果open表的第一个状态不是目的状态，则算法利用与之表的第一个状态不是目的状态，则算法利用与之相匹配的一系列操作算子进行相应的操作来产生它的子状态。相匹配的一系列操作算子进行相应的操作来产生它的子状态。如果某个子状态已在如果某个子状态已在open表（或表（或close
27、d表）中出现过，即该表）中出现过，即该状态再一次被发现时，则通过刷新它的祖先状态的历史记录，状态再一次被发现时，则通过刷新它的祖先状态的历史记录，使算法极有可能找到到达目的状态的更短的路径使算法极有可能找到到达目的状态的更短的路径 接着，接着，A搜索算法搜索算法open表中每个状态的估价函数值，按照值表中每个状态的估价函数值，按照值的大小重新排序，将值最小的状态放在表头，使其第一个被的大小重新排序，将值最小的状态放在表头，使其第一个被扩展。扩展。 三、启发式搜索三、启发式搜索第五章 搜索技术42A(-5)B(-3)C(-4)D(-6)E(-5)F(-3)G(-4)H(-3)IJKL(-5)M(
28、-5) NO(-2)P(-3)QRSTU(-3)三、启发式搜索三、启发式搜索第五章 搜索技术43 例例5.7 利用A搜索算法求解八数码问题的搜索树，其评估函数定义为 ：状态的深度，每步为单位代价。 ：以“不在位”的数码数作为启发信息的度量。)(nd)()()(nwndnf)(nw三、启发式搜索三、启发式搜索-A算法算法第五章 搜索技术44初始s ( 4)2 8 31 6 47 5B( 4)2 8 31 47 6 5C( 4)2 8 31 6 47 5A( 4)2 8 31 6 47 5D( 5)2 8 31 47 6 5E( 5)2 31 8 47 6 5F( 6)2 8 31 47 6 5J
29、 ( 7)2 31 8 47 6 5I ( 5)2 31 8 47 6 5H( 7)2 8 37 1 46 5G( 6)8 32 1 47 6 5K( 5)1 2 38 47 6 5M( 7)1 2 37 8 46 5L( 5)1 2 38 47 6 5目的第五章 搜索技术45 open表和closed表内状态排列的变化情况 三、启发式搜索三、启发式搜索第五章 搜索技术46 如果某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。三、启发式搜索三、启发式搜索-A*算法算法定义：h*(n)为状态n到目的状态的最优路径的代价，则当A算法的启发函数h(
30、n)小于等于h*(n)，即满足h(n)h*(n)，对所有结点n第五章 搜索技术471. 可采纳性可采纳性 当一个搜索算法在最短路径存在时能保证在有限步内找到它，就称它是可采纳的。A*搜索算法的特性搜索算法的特性所有的所有的A A* *算法都是可采纳的算法都是可采纳的。 最优评估函数：最优评估函数：)(*)(*)(*nhngnff f* *(n)(n)：起点出发通过：起点出发通过n n状态而到达目的状态的状态而到达目的状态的最佳路径最佳路径的的总代价总代价值值g g* *(n)(n)：起点到：起点到n n状态的状态的最短路径最短路径代价值代价值h h* *(n)(n)：n n状态到目的状态的状态
31、到目的状态的最短路径最短路径的代价值的代价值第五章 搜索技术482. 2. 单调性单调性 在整个搜索空间都是局部可采纳局部可采纳的。 一个状态和任一个子状态之间的差由差由该状态与其子状态之间之间的实际代价所限定的实际代价所限定。A*搜索算法的特性搜索算法的特性如果某一启发函数满足：如果某一启发函数满足：对所有状态对所有状态ni和和nj，其中，其中nj是是ni的后裔，满足的后裔，满足 ，其中，其中cost(ni,nj)是从是从ni到到nj的实际代价。的实际代价。目的状态的启发函数值为目的状态的启发函数值为0 0或或则称该启发函数则称该启发函数h(n)h(n)是单调的。是单调的。0)(Goalh)
32、,(cos)()(jijinntnhnh第五章 搜索技术493. 信息性信息性 在两个A*启发策略的 中，如果对搜索空间中的任一状态n都有 ，就称策略 具有更多的信息性。 A*搜索算法的特性搜索算法的特性12hh和12( )( )h nh n21hh比信息性越多，所搜索的状态数就越少，但所需要的计算时间越信息性越多，所搜索的状态数就越少，但所需要的计算时间越多。多。第五章 搜索技术0404博弈搜索博弈搜索0303启发式搜索启发式搜索0101图搜索策略图搜索策略0202盲目搜索盲目搜索第五章 搜索技术1914世上第一个计算机游戏1952世界上第一个跳棋程序1979西洋双陆棋程序1997“深蓝”P
33、K卡斯帕罗夫2006浪潮天梭PK许银川2011Watson上场危险边缘四、博弈搜索四、博弈搜索2016AlhoGoPK李世石2017Master、Zero-剪枝算法蒙特卡洛树搜索+信心上限决策深度学习+增强学习+=第五章 搜索技术1. 蒙特卡洛树搜索过程蒙特卡洛树搜索过程选择：选择：以当前棋局为根节点，自上而下地选择一个落子点；扩展：扩展：向选定的节点添加一个或多个子节点；模拟：模拟：对扩展出的节点用蒙特卡罗方法进行模拟；回传：回传：根据模拟结果依次向上更新祖先节点的估计值。存在不足：存在不足：1、选择范围是全体可下子点；2、每次模拟必须一下到底，完成整局模拟直到知道分出胜负为止。第五章 搜索
34、技术信心上限决策信心上限决策1、优先选择到目前为止胜率最大的节点；2、优先选择到目前为止模you拟次数较少的节点)()ln(2nTncXIjjj ：节点j目前的收益（比如获胜概率）；n：是目前为止的总的模拟次数； ：是节点j目前的模拟次数；c：是加权系数jX)(nTjp 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly, And You Will Know Everything. The More You Know, The More Powerful You Will Be写在最后感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings结束语讲师：XXXXXX XX年XX月XX日
