《七讲搜索.ppt》由会员分享，可在线阅读，更多相关《七讲搜索.ppt（60页珍藏版）》请在三一文库上搜索。
1、第七讲 搜 索,程序设计实习,内容提要,枚举与搜索 搜索 广度优先搜索 深度优先搜索 影响搜索效率的因素 POJ 1011 木棍问题,枚举,逐一判断所有可能的方案是否是问题的解,例1：求出A-I这九个字母对应的数字（1-9），使得下式成立（一一对应 ）,枚举,解法： 枚举ABCDE的值，计算乘积，判断是否符合要求。,搜索,搜索：高级枚举 有顺序有策略地枚举状态空间中的结点，寻找问题的解,例题：POJ1077八数码问题,例题：POJ1077八数码问题,状态空间,广度优先搜索（ breadth-first search）,优先扩展浅层结点，逐渐深入； 广度优先搜索算法按结点的层次进行搜索， 本层的
2、结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。,第一层,第二层,第三层,广度优先搜索,广度优先搜索 用队列保存待扩展的结点，从队首队取出结点，扩展出的新结点放入队尾，直到找到目标结点（问题的解）,广度优先搜索,广度优先搜索的代码框架,BFS() 初始化队列； while( 队列不为空 且 未找到目标结点 ) 取队首结点扩展，并将扩展出的结点放入队尾； 必要时要记住每个结点的父结点； ,深度优先搜索（depth-first search）,优先深入遍历靠前的结点； 深度优先搜索就是在搜索树的每一层始
3、终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。 这种方法的搜索树是从树根开始一枝一枝逐渐形成的。,深度优先搜索,深度优先搜索 可以用栈实现，在栈中保存从起始结点到当前结点的路径上的所有结点；,深度优先搜索,深度优先搜索的栈实现（非递归）框架,DFS() 初始化栈； while( 栈不为空 且 未找到目标结点 ) 取栈顶结点扩展，扩展出的结点放回栈顶； ,深度优先搜索,深度优先搜索的递归框架,type node； void DFS(int depth) for(node的每一个可行变化) 改变node；
4、DFS(depth + 1)； 恢复node； ,此种做法需要一个全局数组array来存放每个走过的node，arraydepth就是进入DFS函数时需要扩展的节点。,判重,判重 新扩展出的结点如果和以前扩展出的结点相同，则这个新节点就不必再考虑。 如何判重？,重复?,判重,需要考虑的问题 状态数目巨大，如何存储？ 怎样才能较快的找到重复结点？,判重,合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。 判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了
5、标志位序列可以用字符数组存放。每个字符8个bit，可以存放8个状态标志位。位序列最多需要99位，因此存放位序列的数组需要99/8 + 1个字节 48427562字节。 如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8),判重,合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。 此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。,判重,合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别,方案二：为结点编号 把每个结点都看一个排列，以此排列在
6、全部排列中的位置作为其编号 排列总数：9!=362880 只需要一个整数(4字节)即可存下一个结点 判重用的标志数组只需要362880字节即可。 此方案比方案1省空间； 此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。,判重,时间与空间的权衡 对于状态数较小的问题，可以用最直接的方式编码以空间换时间； 对于状态数太大的问题，需要利用好的编码方法以时间换空间； 具体问题具体分析。,输入数据： 2 3 4 1 5 x 7 6 8 输出结果： ullddrurdllurdruldr,用广搜解决八数码问题,2 3 4 1 5 7
7、6 8,输入数据代表,移动序列中： u 表示使空格上移 d 表示使空格下移 r 表示使空格右移 l 表示使空格左移,1 2 3 4 5 6 7 8,输出数据：是一个移动序列，使得移动后结果变成,/本程序在ai上会超内存，在acm上能过 #include using namespace std; int nGoalStatus; /目标状态 unsigned char szFlag48427562; /节点是否扩展的标记 char szResult1000000; char szMoves1000000; /移动步骤 int anFather1000000; /父节点指针 int MyQueue
8、1000000; /状态队列 int nQHead; int nQTail; char sz4Moves = “udrl“;/四种动作,八数码例子程序,int NineToTen( char * s ) /九进制字符串转十进制 int nResult = 0; for( int i = 0; si; i + ) nResult *= 9; nResult += si - 0; return nResult; int GetBit( unsigned char c,int n) return ( c n ) ,int TenToNine( int n, char * s) /十进制数转九进制字符
9、串。可能有前导0 /返回0的位置 int nZeroPos; int nBase = 1; int j = 0; while( nBase = 1 ); sj = 0;,/判是否要加前导0 if( j 0; i -) si = si-1; s0 = 0; return 0; return nZeroPos; ,int NewStatus( int nStatus, char cMove) /求从nStatus经过 cMove 移动后得到的新状态 /若移动不可行则返回-1 char szTmp20; int nZeroPos = TenToNine(nStatus,szTmp); switch(
10、 cMove) case u: if( nZeroPos - 3 8 ) return -1; else szTmpnZeroPos = szTmpnZeroPos + 3; szTmpnZeroPos + 3 = 0; break;,case l: if( nZeroPos % 3 = 0) return -1; else szTmpnZeroPos = szTmpnZeroPos -1; szTmpnZeroPos -1 = 0; break; case r: if( nZeroPos % 3 = 2) return -1; else szTmpnZeroPos = szTmpnZeroP
11、os + 1; szTmpnZeroPos + 1 = 0; break; return NineToTen(szTmp); ,bool Bfs(int nStatus) int nNewStatus; nQHead = 0; nQTail = 1; MyQueuenQHead = nStatus; while ( nQHead != nQTail) /队列不为空 nStatus = MyQueuenQHead; if( nStatus = nGoalStatus ) /找到目标状态 return true; for( int i = 0;i 4;i + ) /尝试4种移动 nNewStatu
12、s = NewStatus(nStatus,sz4Movesi); if( nNewStatus = -1 ) continue; /不可移，试下一种移法,int nByteNo = nNewStatus / 8; int nBitNo = nNewStatus % 8; if( GetBit( szFlagnByteNo,nBitNo) continue; /如果扩展标记已经存在， /则不能入队 /设上已扩展标记 SetBit( szFlagnByteNo,nBitNo,1); /新节点入队列 MyQueuenQTail = nNewStatus; anFathernQTail = nQHe
13、ad; /记录父节点 /记录本节点是由父节点经什么动作而来 szMovesnQTail = sz4Movesi; nQTail +; /end for nQHead +; /end while return false; ,int main() nGoalStatus = NineToTen(“123456780“); memset(szFlag,0,sizeof(szFlag); char szLine50; char szLine220; cin.getline(szLine,48); int i,j; /将输入的原始字符串变为九进制字符串 j = 0; for( i = 0; szLin
14、ei; i + ) if( szLinei != ) if( szLinei = x ) szLine2j+ = 0; else szLine2j+ = szLinei; szLine2j = 0;,if( Bfs(NineToTen(szLine2) int nMoves = 0; int nPos = nQHead; do szResultnMoves+ = szMovesnPos; nPos = anFathernPos; while( nPos); for( int i = nMoves -1; i = 0; i - ) cout szResulti; else cout “unsol
15、vable“ endl; ,用深搜解决本题不好。如用递归实现，不作特殊处理的话，很容易就导致递归层数太多而栈溢出。 可以不写递归，自己用大数组实现一个栈。这可以避免栈溢出。但是可能导致输出结果的步数太多（几万步），这样交到POJ上会 Output limit exceeded 如果运气很坏，也可能数组会不够用。,用深搜解决八数码问题,深度优先搜索举例 void Queen( int n) /摆放第n行以及以后的皇后(行号从0开始算) if( n = QueenNum ) /前QueenNum行都成功摆好了，记下摆法 memcpy(anResultnFoundNum+,anQueen,sizeo
16、f(anQueen); return ; for( int i = 0;i QueenNum; i + ) /尝试第n行所有位置 int j; for( j = 0; j n; j + ) /对每个位置，判断是否和已经摆好的皇后冲突 if( i = anQueenj | abs( i - anQueenj) = abs(n - j ) break; if( j = n ) /如果没有冲突，则第n行摆好了，记下来，再摆第n+1行 anQueenn = i; Queen(n+1); ,广搜与深搜的比较,广搜一般用于状态表示比较简单、求最优策略的问题 需要保存所有扩展出的状态，占用的空间大； 每次扩
17、展出结点时所走过的路径均是最短路； 如果目标在搜索空间中隐藏得不是太深，那么广度优先搜索的性能会很好。 深搜几乎可以用于任何问题 只需要保存从起始状态到当前状态路径上的结点； 根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择。,影响搜索效率的因素,影响搜索效率的因素 搜索对象(枚举什么） 搜索顺序（先枚举什么，后枚举什么） 剪枝(及早判断出不符合要求的情况）,例题： POJ1011 木棒问题,问题描述： 乔治拿来一组等长的棍子，将它们随机地裁断（截断后的小段称为木棒），使得每一节木棒的长度都不超过50个长度单位。然后他又想把这些木棒恢复到裁截前的状态，但忘记了棍子的初始长度。请你设计一
18、个程序，帮助乔治计算棍子的可能最小长度。每一节木棒的长度都用大于零的整数表示。,输入数据 由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，是零。 输出要求 为每个案例，分别输出木棒的可能最小长度，每个案例占一行。 输入样例 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0 输出样例 6 5,解题思路,初始状态：有N节木棒 最终状态：这N节木棒恰好被拼接成若干根等长的棍子(裁前的东西称为棍子） 枚举什么？ 枚举所有有可能的棍子长度。从最长的那根木棒的长度一直枚举到木棒长度总和
19、的一半，对每个假设的棍子长度试试看能否拼齐所有棍子。,在拼接过程中，要给用过的木棒做上标记，以免重复使用。 拼好前i根棍子，结果发现第i+1根拼不成了，那么就要推翻第i根的拼法，重拼第i根直至有可能推翻第1根棍子的拼法。,搜索题，首先要解决一个问题：按什么顺序搜索？ 把木棒按长度排序。每次选木棒的时候都尽量先选长的。为什么？,因为短木棒比较容易用来填补空缺。一根长木棒，当然比总和相同的几根短木棒要优先使用。,搜索题，还要解决一个问题：如何剪枝（就本题而言，即尽可能快地发现一根拼好的棍子需要被拆掉，以及尽量少做结果不能成功的尝试。）,剪枝1：,每次开始拼第i根棍子的时候，必定选剩下的木棒里最长的
20、一根，作为该棍子的第一根木棒。对此决不后悔。 即: 就算由于以后的拼接失败，需要重新调整第i根棍子的拚法，也不会考虑替换第i根棍子中的第一根木棒（换了也没用）。如果在此情况下怎么都无法成功，那么就要推翻第i-1根棍子的拚法。如果不存在第i-1根棍子，那么就推翻本次假设的棍子长度，尝试下一个长度。,1,2,3,棍子i,可以考虑把2,3换掉重拼棍子i,但是把1换掉是没有意义的,剪枝1：,为什么替换第i根棍子的第一根木棒是没用的？ 因为假设替换后能全部拼成功，那么这被换下来的第一根木棒，必然会出现在以后拼好的某根棍子k中。那么我们原先拼第i根棍子时, 就可以用和棍子k同样的构成法来拼，照这种构成法拼
21、好第i根棍子，继续下去最终也应该能够全部拼成功。,1,棍子k,剪枝2： 不要希望通过仅仅替换已拼好棍子的最后一根木棒就能够改变失败的局面。,1,2,3,假设由于后续拼接无法成功，导致准备拆除已经拼好的某根棍子，如下：,将 3 拆掉，留下的空用其他短木棒来填，是徒劳的,棍子i,剪枝2：,1,2,假设替换3后最终能够成功，那么3必然出现在后面的某个棍子k里。将棍子k中的3和棍子i中用来替换3的几根木棒对调，结果当然一样是成功的。这就和i原来的拚法会导致不成功矛盾。,棍子i,3,棍子k,已拼接部分,未拼接部分,长度为L的棍子,长度为L1的未拼接木棒，共有N1根,长度为L2的未拼接木棒，共有N2根,长
22、度为L3的未拼接木棒，共有N3根,如果某次拼接选择长度为L1的木棒，导致最终失败，则在同一位置尝试下一根木棒时，要跳过所有长度为L1的木棒。,剪枝3：,bool Dfs(int nUnusedSticks, int nLeft ) ; 表示: 当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft, 那么在这种情况下能全部否拼成功。,Dfs的基本递推关系： bool Dfs(int nUnusedSticks, int nLeft) 找一根长度不超过nLeft的木棒(假设长为len)，拼在当前棍子上，然后 return Dfs(nUnusedStic
23、ks 1,nLeft len ); ,Dfs的终止条件之一： bool Dfs(int nUnusedSticks, int nLeft ) if( nUnusedSticks = 0 ,#include #include #include int T, S; int L; int anLength65; int anUsed65; int i,j,k; int Dfs(int nUnusedSticks, int nLeft); int MyCompare( const void * e1, const void * e2) int * p1, * p2; p1 = (int * ) e1;
24、 p2 = (int * ) e2; return * p2 - * p1; ,main() while(1) cin S; if( S = 0 ) break; int nTotalLen = 0; for( int i = 0; i anLengthi; nTotalLen += anLengthi; qsort(anLength,S,sizeof(int),MyCompare);,for( L = anLength0; L nTotalLen / 2 ) cout nTotalLen endl; / while ,上一根同样长度的木棒为什么还没用？必然是因为刚刚用过，并且发现用了后不行，
25、才将其 anUsed标志置回0,int Dfs( int nUnusedSticks, int nLeft) / nLeft表示当前正在拼的棍子和 L 比还缺的长度 if( nUnusedSticks = 0 ,if ( Dfs( nUnusedSticks - 1, nLeft - anLengthi) return true; else anUsedi = 0;/说明本次不能用第i根 /第i根以后还有用 if( anLengthi = nLeft | nLeft = L) return false; /剪枝2、1 return false; ,剪枝 4：,拼每一根棍子的时候，应该确保已经拼
26、好的部分，长度是从长到短排列的。即拼的过程中要排除类似下面这种情况：,1,未完成的棍子i,2,3,木棒3 比木棒2长，这种情况的出现是一种浪费。因为要是这样往下能成功，那么2, 3 对调的拚法肯定也能成功。由于取木棒是从长到短的，所以能走到这一步，就意味着当初将3放在2的位置时，是不成功的,剪枝 4：,排除办法：每次找一根木棒的时候，只要这不是一根棍子的第一条木棒，就不应该从下标为0的木棒开始找，而应该从刚刚(最近）接上去的那条木棒的下一条开始找。这样，就不会往2后面接更长的3了。,1,2,为此，要设置一个全局变量 nLastStickNo ，记住最近拼上去的那条木棒的下标。,int Dfs(
27、 int nUnusedSticks, int nLeft) / nLeft表示当前正在拼的棍子和 L 比还缺的长度 if( nUnusedSticks = 0 ,if ( Dfs( nUnusedSticks - 1, nLeft - anLengthi) return true; else anUsedi = 0;/说明本次不能用第i根 /第i根以后还有用 if( anLengthi = nLeft | nLeft = L) return false;/剪枝2、1 return false; ,作业,ai2787 算24,一位顾客要预定一张从New York到Los Angeles的航班机票，下面是航班线路，请你为顾客找一种购票方案。,一位顾客要预定一张从New York到Los Angeles的航班机票，下面是航班线路，请你为顾客找一种购票方案。,