搜索方法.pptx

搜索方法及竞赛题目讲解彭超 2006.8状态空间搜索v搜索被称为“通用解题法”，在算法中占有重要的地位。v有巨大的局限性和自身的灵活性。v首先建立“状态空间”然后“盲目”搜索。常用方法：深度优先搜索，广度优先搜索，双向广度优先搜索，迭代加深，v优化策略：剪枝、启发式、状态空间v状态：问题在某一时刻进展状况的数学描述。v状态转移：问题从一种状态到另一种或几种状态的操作操作。v状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。v搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。例：过河问题v某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?例：过河问题v状态：建立四元组（人，狗，鸡，米）。用0表示在左岸，1表示在右岸。v起始状态(0,0,0,0)，终止状态(1,1,1,1)v状态转移规则：(a,b,c,d)(1-a,1-b,c,d)（当a=b）(1-a,b,1-c,d)（当a=c）(1-a,b,c,1-d)（当a=d）(1-a,b,c,d)v约束：(a,b,c,d)中，当ab时bc；当ac时cd例：过河问题v搜索：(0,0,0,0)(1,1,0,0)(1,0,1,0)(0,0,1,0)(1,0,1,1)(1,0,0,1)(1,1,1,0)(1,0,0,0)例：过河问题v搜索：(1,0,1,1)(0,0,0,1)(1,1,0,1)(0,1,0,1)(1,1,1,1)ok (0,0,1,0)(1,0,1,1)(0,0,1,1)(0,0,1,1)(1,1,1,0)(0,0,1,0)(1,0,1,1)(0,0,1,1)(0,1,0,0)(1,1,0,1)(0,1,0,1)(1,1,1,1)ok (0,1,1,0)例：过河问题v搜索在“图”中进行，但图不需要事先建立（“隐式图”）。v搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。v搜索树的结点个数、分枝数、深度，决定着搜索的效率。例：过河问题v搜索树过河问题的程序实现v普通状态可以用4个整数表示v压缩状态用4个bit表示(char型有8个bit，足够用)。v用深度优先(DFS,Depth First Search)或广度优先(BFS,Breath First Search)。回溯(DFS)的基本结构判断是否到了底层。是，则返回上一层否则，对于各种可能情况：if possible 加入标记 进入下一层 清除标记 else if 所有情况列举完毕 返回上一层这个结构是普遍适用的。任何递归递归的DFS程序都能套进去。DFSvzju 1711Sum It Up vzju 1004Anagrams by Stackvzju 1204Additive equationsvzju 1984Genetic Code vzju 1457Prime Ring Problemvzju 1008Gnome Tetravexvzju 1411Anniversaryvzju 1267Mapping the Routevzju 1482Partitionsvzju 1990Subway Tree SystemsSum It Up(zju 1711)v输入正整数t、n，然后是n个正整数(单调非递增)。若n个数中某几个数的和是t，输出这些加法表达式(表达式不重复输出)；无解输出“NONE”输入：输入：4 7 4 4 3 2 2 1 1输出：输出：Sums of 4:43+12+22+1+1输入：5 3 2 1 1输出：Sums of 5:NONESum It Up(zju 1711)v状态：计算中间值rv转移规则：r r-ai（取第i个数ai）r（不取第i个数）v起始状态：所输入的t 中止状态：04041-1取4不取4取34不取3取21不取2-1取21不取20取11不取10取11不取1输入：4 6 4 3 2 2 1 1搜索树如下：Anagrams by Stack(zju 1004)v有一个字母序列，对它每个元素进行入栈、出栈操作。判断是否能得到指定输出序列，如果可以，输出相应的栈操作。输入：输入：madamadamm 输出：输出：i i i i o o o i o oi i i i o o o o i oi i o i o i o i o oi i o i o i o o i o Prime Ring Problem(zju 1457)vn个数排一圆环，要求相邻两个数和为素数。输入：输入：68输出：输出：Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2Genetic Code(zju 1984)v输入整数n,输出一个长度为n的由N、O、P组成的字符串，要求任意相邻子串不相同。输入：输入：1210200输出：输出：NNONONPNOPNPONONPNOPNPONOPNONPNOP广度优先搜索BFSV3V2V4V1V6V5广度优先遍历V3V2V4V1V6V5BFS程序的基本结构定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;这个结构是普遍适用的。任何非递归非递归的BFS程序都能套进去。例无向图如下，边权均为无向图如下，边权均为1，求，求V1到到V3的最短路径的最短路径V3V2V4V1V6V5给图定义邻接矩阵int G66：0 1 0 1 1 11 0 1 1 0 00 1 0 1 1 11 1 1 0 0 11 0 1 0 0 11 0 1 1 1 0定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1队列结点记录两个信息1：顶点编号2：步数定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v10定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v10V1不是终点定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v10定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v21定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V2不是终点v21定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v21定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是终点定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v51定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v61定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v32定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是终点，结束搜索，输出2BFSvzju 1091Knight Movesvzju 1047Image Perimetersvzju 1103Hike on a Graphvzju 1649Rescue vzju 1310Robot vzju 1136Multiplevzju 1530Find The Multiplevzju 1301The New VillaKnight Moves(zju 1091)v国际象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？输入：输入：a1 h8输出：输出：To get from a1 to h8 takes 6 knight moves.a b c d e f g h12345678h8a1Divisibility(zju 2042)v输入N、K,然后输入N个整数，N个整数可列出若干加减运算式；若存在一个算式，它的值能被K整除,输出“Divisible”，否则输出“Not divisible”.输入：24 717 5 -21 154 517 5 -21 15输出：Divisible Not divisibleHoledox Moving(zju 1361)v一条长度为L“贪吃蛇”在n*m的迷宫中，求它走到出口的最少步数。(2L 8;1n,m 20)输入：输入：5 6 44 14 23 23 132 33 33 40 0 0输出：输出：Case 1:9The New Villa(zju 1301)v别墅里有r个房间，编号1,2,r。告诉你房间的连通关系以及各房灯的开关位置。初始，除了房间1，其他房灯都是灭的。主人希望从1走到r，而且进入房间时，房灯是打开的；离开房间能把灯关掉。(r 10)输入：输入：3 3 41 21 33 21 21 32 13 22 1 22 11 11 20 0 0输出：输出：Villa#1The problem can be solved in 6 steps:-Switch on light in room 2.-Switch on light in room 3.-Move to room 2.-Switch off light in room 1.-Move to room 3.-Switch off light in room 2.Villa#2The problem cannot be solved.高级搜索v“8数码”游戏的搜索问题。4583276145213876高级搜索v“华容道”游戏的搜索问题。张张飞飞曹曹 操操马马超超赵赵云云关关 羽羽黄黄忠忠兵兵兵兵兵兵兵兵