ACM培训第八讲-搜索

ACM专题讲座——搜索算法ACM程序设计第八讲-搜索湖南工学院张新玉[e-mail]专题讲座——搜索算法搜索算法1.搜索问题2.搜索方法分类3.回溯方法4.一般图搜索算法5.启发式搜索算法ACM专题讲座——搜索算法1.搜索问题人类的思维过程，可以看作一个搜索过程。我们遇到的很多智力游戏问题，如传教士和野人问题。有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可乘坐2个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在河的两岸以及船上传教士人数不能少于野人的人数？对这个问题，在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？这就是搜索问题。ACM专题讲座——搜索算法1.搜索问题对这类问题，一般我们都转换为状态空间的搜索问题。如传教士和野人问题，可用在河左岸的传教士人数、野人人数和船的情况来表示。即，初始时状态为（3，3，1），结束状态为（0，0，0），而中间状态可表示为（2，2，0）、（3，2，1）等等。初始状态结束状态LRLRm30m03c30c03B10B01ACM专题讲座——搜索算法1.搜索问题由此，可以看出这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图：SgS0解路径搜索空间全状态空间ACM专题讲座——搜索算法2.搜索方法分类不可撤回方法试探性方法回溯方法图搜索方法ACM专题讲座——搜索算法3.回溯方法回溯方法，属于盲目搜索的一种，它是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或已试探过所有可能仍找不到问题的解为止。ACM专题讲座——搜索算法3.回溯方法•例：皇后问题QQQQACM专题讲座——搜索算法3.回溯方法()()ACM专题讲座——搜索算法3.回溯方法()()((1,1))QACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))QQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))QACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))QQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))ACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))QACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))QQQACM专题讲座——搜索算法3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQACM专题讲座——搜索算法3.回溯方法•递归的思想：当前状态目标状态gACM专题讲座——搜索算法3.回溯方法•算法描述：BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。ACM专题讲座——搜索算法3.回溯方法1,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);ACM专题讲座——搜索算法3.回溯方法7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);ACM专题讲座——搜索算法4.一般图搜索算法•问题的引入：回溯搜索：只保留从初始状态到当前状态的一条路径图搜索：保留所有已经搜索过的路径如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。ACM专题讲座——搜索算法4.一般图搜索算法•问题的引入：回溯搜索：只保留从初始状态到当前状态的一条路径图搜索：保留所有已经搜索过的路径如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。ACM专题讲座——搜索算法4.一般图搜索算法•一些基本概念：节点深度：根节点深度=0其它节点深度=父节点深度+10123ACM专题讲座——搜索算法4.一般图搜索算法•一些基本概念：路径:设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值:一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点:生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。ACM专题讲座——搜索算法4.一般图搜索算法•一般性图搜索算法：1:G←S,OPEN←(S);建立一个搜索图G,它只含有初始节点S,建立一个OPEN表(今后它用于存储生成的节点),开始它只含有初始节点S。2:CLOSED←();建立一个CLOSED表(今后它用于存储已扩展节点或将要扩展的某个节点),它的初始状态为空表。3:LOOP:ifOPEN=()thenreturnFAIL;进入循环。如果OPEN表已空,说明没有节点可扩展,就返回FAIL,即失败。4:n←FIRST(OPEN),CLOSED←(n,CLOSED);从OPEN表中取出一个节点n,将其放入CLOSED表中。5:ifn∈目标集thenreturn[s→…→n];如果n为目标节点,则沿着G中从n到s的链指针得出一条路径,并以此返回。ACM专题讲座——搜索算法4.一般图搜索算法•一般性图搜索算法(续)：6:M←expand(n),G'←G,G←{M,G'};扩展节点n,建立集合M,并把M中的节点作为n的后继者加入G中。7:对M中的所有节点m(1)ifmG'then建立指针m→n,OPEN←CONS(M,OPEN);对M中原来不在G中的节点建立一个从这些节点到n的指针,并把它们加入OPEN表。(2)ifm∈OPENthen根据其扩展路径确定是否应将它们的指针指向n。(3)ifm∈CLOSEDthen根据其扩展路径确定是否应改变m的后代的指针。8:对OPEN中的节点按某种原则重新排序；9:GOLOOP；ACM专题讲座——搜索算法4.一般图搜索算法•节点类型：…...…...…...…...…...mjmkmlACM专题讲座——搜索算法4.一般图搜索算法•广度优先搜索法：该方法从初始节点开始,顺序扩展生成下一级各子节点,放在OPEN表中已有的节点后面(实现先生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法认为同一级各节点对问题求解的价值是同等的,因而对全部节点沿广度进行横向扫描,按各节点生成的先后次序,先生成、先检查、先扩展,沿广度遍历所有节点。这种方法只要问题有解,即若树图上存在目标节点,经搜索一定能找到。所以,广度优先搜索法是完备的,是一种推理算法。但是,在问题大节点多,且目标节点距离初始节点较远时将会产生许多无用节点,搜索效率低,还可能产生组合爆炸。因此,这种方法较适宜问题不大的环境中。ACM专题讲座——搜索算法4.一般图搜索算法•广度优先搜索算法：1:G:=G0(G0=s),OPEN:=(s),CLOSED:=();2:LOOP:IFOPEN=()THENEXIT(FAIL);3:n:=FIRST(OPEN);4:IFGOAL(n)THENEXIT(SUCCESS);5:REMOVE(n,OPEN),ADD(n,CLOSED);6:EXPAND(n)→{mi},G:=ADD(mi,G);7:IF目标在{mi}中THENEXIT(SUCCESS);8:ADD(OPEN,mj),并标记mj到n的指针;9:GOLOOP;ACM专题讲座——搜索算法4.一般图搜索算法•例:8数码难题•在一个3×3的方框内放有8个编号的小方块，紧邻空位的小方块可以移入到空位上，通过平移小方块可将某一布局变换为另一布局。请给出从初始状态到目标状态移动小方块的操作序列。2318476512384765ACM专题讲座——搜索算法23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654ACM专题讲座——搜索算法4.一般图搜索算法•广度优先搜索的性质：1.当问题有解时，一定能找到解2.当问题为单位耗散值，且问题有解时，一定能找到最优解3.方法与问题无关，具有通用性4.效率较低5.属于图搜索方法ACM专题讲座——搜索算法4.一般图搜索算法•深度优先搜索法：该方法从初始节点开始,顺序扩展生成下一级各子节点,放在OPEN表中已有的节点前面(实现后生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法每一次扩展最晚生成的子节点,沿着最晚生成的子节点分支,逐级纵向深入发展。这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上,则可较快地得到解。但是,如果目标节点不在此分支上,不回溯就不可能得到解。所以,深度优先搜索是不完备的,只是推理步骤。如果回溯,不难证明其平均效率与广度优先搜索法相同。因此,深度优先搜索法如果没有启发信息,很难有实用价值。ACM专题讲座——搜索算法4.一般图搜索算法•深度优先搜索算法：1:G:=G0(G0=s)