广度优先搜索

1、程序设计实习第十八讲 广度优先搜索内容提要o 广度优先搜索的基本思想o POJ1077八数码问题n 广搜n 双向广搜(扩展，不要求)n A*(扩展，不要求)o 小结：影响搜索效率的因素2广度优先搜索o广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况n搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。n假设有两个表：Open表存放待处理节点，Closed表存放处理完节点nOpen表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。 广度优先搜索o

2、 两个状态的集合n : 未处理完的状态n : 已处理的状态o 从中选择被演化状态的原则：离初态S0距离最近的状态sn S0到s的距离：从S0到达s使用的动作数量o 实现方法：用queue表示n 每次取queue头部的状态演化n 每次演化出的状态s若不属于，则s将压入queue的尾部深搜 vs. 广搜o 深搜1-2-4-8-5-6-3-7o 广搜1-2-3-4-5-6-7-8广搜算法o广度优先搜索算法如下：（用 QUEUE） (1) 把初始节点S0放入Open表中； (2) 如果Open表为空，则问题无解，失败退出； (3) 把Open表的第一个节点取出放入Closed表，并记该节点为n； (4

3、) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出； (5) 若节点n不可扩展，则转第(2)步； (6) 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。例题：POJ1077八数码问题o 八数码问题是人工智能中的经典问题o POJ1077八数码问题：经典搜索问题n 有一个3*3的棋盘，其中有0-8共9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态1 2 34 5 67 8 0的步数最少的解？ 12345678823146577例题：POJ1077八数码问题o 状态空间82341657823415768234

4、165 78241357682341576823416578广度优先搜索o 广度优先搜索（bfs）n 优先扩展浅层节点，逐渐深入第一层第二层第三层8234165782341576823416578241357682341576823416579n 用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）823416578234157682413576823415768234165710广度优先搜索o 广度优先搜索的代码框架Void BFS( )初始化队列while(队列不为空且未找到目标节点)取队首节点扩展，并将扩展出的节点放入队尾；必要时要记住每个节点的

5、父节点；11关键问题：判重o 判重n 新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑n 如何判重？重复?823416578234157682341650782413576823415768234165712关键问题：判重o 需要考虑的问题n 状态数目巨大，如何存储？n 怎样才能较快的找到重复节点？时间空间13判重o 合理编码，减小存储代价n 不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。 （ 228 99=387,420,489 229）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志

6、位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8 + 1个字节 48,427,562字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8)14判重o 合理编码，减小存储代价n 不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。15判重o 合理编码，减小存储代价n 不同的编码方式所需要的存储空间会有

7、较大差别82341657方案二：为节点编号把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个节点判重用的标志数组只需要362,880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。16判重o 时间与空间的权衡n 对于状态数较小的问题，可以用最直接的方式编码以空间换时间n 对于状态数太大的问题，需要利用好的编码方法以时间换空间n 具体问题具体分析17输入数据：2 3 4 1 5 x 7 6 8输出结果：ullddrurdl

8、lurdruldr 2 3 4 1 5 7 6 8 输入数据代表：移动序列中u 表示使空格上移d 表示使空格下移r 表示使空格右移l 表示使空格左移1 2 3 4 5 6 7 8 输出数据是一个移动序列，使得移动后结果变成用广搜解决八数码问题18八数码例子程序o 采用方案1的非递归方案：数据结构n用一个九进制字符串表示一个节点，其中有且仅有一个0（表示空格）-因此若九进制串中没有0，则0一定是在最高位n设一个48427562位字符型标志位序列数组szFlag，标识每个状态是否已扩展n设一个队列MyQueue存放搜索过程中的可能状态，根据问题定义，状态总数362880。考虑到搜索过程中可能存在的

9、重复状态，其大小设为400000。n为简化计算，设置与MyQueue同样大小的数组anFather存放父节点指针、数组szMoves存放从父节点到当前节点的移动步骤n设置一个结果队列，为防止溢出，设置与MyQueue同样大小19八数码例子程序o 采用方案1的非递归方案：关键处理逻辑n Main程序1.将输入的原始字符串变为九进制字符串;2.用BFS过程看是否可以达到目标状态;3.若能达到，通过anFather数组找到成功的状态序列;4.根据数组szMoves找到相应的移动步骤，并输出.n BFS过程输入：初始状态 输出：成功/失败；若成功， anFather、 szMoves20八数码例子程序

10、o 采用方案1的非递归方案：关键处理逻辑n BFS中的关键问题：1）如何进行状态扩展？2）状态中0的位置与cMove动作间的关系？3）如何计算求从nStatus经过 cMove 移动后得到的新状态（定义为函数NewStatus ）？4）如何判断扩展标记已经存在？5）对未扩展状态，如何置已扩展标记(定义为函数SetBit )？6）字符串形式的9进制数到其整型值的互相转换函数（定义为NineToTen和TenToNine）21#include #include using namespace std;int nGoalStatus; /目标状态bitset Flags; /节点是否扩展的标记cha

11、r szResult400000; /结果char szMoves400000; /移动步骤 ： u/d/r/l int anFather400000; /父节点指针int MyQueue400000; /状态队列，状态总数362880int nQHead; int nQTail;char sz4Moves = udrl;/四种动作八数码例子程序22int NineToTen( char * s ) /九进制字符串转十进制int nResult = 0;for( int i = 0; si; i + ) nResult *= 9;nResult += si - 0;return nResult

12、;23int TenToNine( int n, char * s) /十进制数转九进制字符串。可能有前导0，返回0的位置int nZeroPos;int nBase = 1;int j = 0;while( nBase = 1 );sj = 0;/串结束符/判断是否要加前导0，此时第0位即为0if( j 0; i -)si = si-1;s0 = 0;return 0;return nZeroPos;24int NewStatus( int nStatus, char cMove) /求从nStatus经过 cMove 移动后得到的新状态。若移动不可行则返回-1char szTmp20;in

13、t nZeroPos = TenToNine(nStatus,szTmp);/返回空格的位置switch( 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(

14、nZeroPos % 3 = 2) return -1; /空格在第三列else szTmpnZeroPos = szTmpnZeroPos + 1;szTmpnZeroPos + 1 = 0;break;return NineToTen(szTmp);25bool Bfs(int nStatus)int nNewStatus;nQHead = 0;nQTail = 1;MyQueuenQHead = nStatus;while ( nQHead != nQTail) /队列不为空nStatus = MyQueuenQHead;if( nStatus = nGoalStatus ) /找到目标

15、状态 return true;for( int i = 0;i = 0; i - ) cout szResulti;elsecout unsolvable endl; return 0;27问题o 前述程序中，是否有状态被重复扩展？n 初始状态。为避免此重复， 应在BFS初始化时对初始状态进行置位o 前述程序中，8数码问题的有解性判定n 如果所有结点都扩展完还没有达到目标状态，则问题无解，失败退出o 是否有更节省存储空间的做法，例如可以不用几个大数组？n 一种可能方案：使用2个链表分别存队列和结果28广搜的解法二：链表表示o 基本思想：定义8数码结点类CEight,它有两个指针open_nex

16、t和parent，分别指向BFS扩展结点的下一个open节点和父结点（若当前结点为目标结点，通过parent可以得到解路径）n 不需要设置标志位序列数组szFlagn 用链表来表示状态队列MyQueueo 其他要求n 目标结点可以支持重新设定，这样可以用于计算任意两个结点间的距离n 输出结果将解路径打印出来2 8 3 1 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 52 31 8 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 6 47 52 81 4 37 6 5

17、2 8 31 4 57 68 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 3 6 41 7 52 8 31 67 5 42 81 4 37 6 52 8 31 4 57 68 32 1 47 6 58 1 32 47 6 52 8 37 46 4 52 8 37 1 46 51 2 37 8 4 6 51 2 38 47 6 5图3.4八数码难题的宽度优先搜索树2 8 31 47 6 51S023456789101112131415161718192021222324252627Sg八数码问题：任意两结点间路径实现细节(1)o

18、8数码结点类CEightn =：两对象赋值，或用数组给对象赋值n =：两对象是否相等，或对象和一用数组存储的结点是否相等o 普通函数n 四类移动操作move_left/right/up/downn 判断有无重复existed：链表遍历n 判定是否有解icansolve八数码问题有解性的判定o 八数码问题的一个状态实际上是09的一个排列，对于任意给定的初始状态和目标，不一定有解，即从初始状态不一定能到达目标状态。n因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。 o 如果一个数字08的随机排列，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=(F(X)，如果Y

19、为奇数则称该排列是奇排列，如果Y为偶数则称该排列是偶排列。n871526340排列的 Y=0+0+0+1+1+3+2+3+0=10，10是偶数，所以是偶排列。n871625340排列的Y=0+0+0+1+1+2+2+3+0=9 9是奇数，所以是奇排列。 n因此，可以在运行程序前检查初始状态和目标状态的奇偶性是否相同，相同则问题可解，应当能搜索到路径。否则无解。实现细节(2)o 广搜过程让链表头指针open_head和尾指针open_tos指向初始节点S；while(open_head不为空且找到标志为假)if(*open_head=Target) 找到标志为真; break;Repeat 四种

20、动作 分别执行一种动作； if (动作执行成功&移动后新状态在链表中无重复) 1. 从该新状态生成新的CEight对象，使其父结点为 *open_head，使其open_next为NULL； 2. 通过尾指针open_tos将新CEight对象加入队列； 移动open_head指针; #include iostreamusing namespace std;static int target9=1,2,3,4,5,6,7,8,0;class CEightprivate:int num9; /结点数组int deapth; /深度public:CEight* parent; /父指针CE

21、ight* open_next; /扩展指针CEight(int init_num9); /用数组构造对象CEight(void); /构造函数，使用缺省初始化 int get_deapth(void); /取深度void get_numbers_to(int other_num9); /将数序列拷贝到另一数组void set_num(int other_num9); /将另一数组的数序列设置对象void show(void); /输出结果CEight& operator=(CEight&); /两对象赋值CEight& operator=(int other_num9

22、); /用数组给对象赋值int operator=(CEight&); /两对象是否相等int operator=(int other_num9); /对象和数组是否相等;注意：本解法与POJ要求不完全相同，但很容易修改和移植CEight:CEight(int init_num9)for (int i=0;i9;i+)numi=init_numi;CEight:CEight()for (int i=0;i9;i+)numi=i;int CEight: get_deapth(void)return deapth;void CEight:get_numbers_to(int other_n

23、um9)for (int i=0;i9;i+)other_numi=numi;void CEight:set_num(int other_num9)for (int i=0;i9;i+)numi=other_numi;void CEight:show() for (int i=0;i9;i+) coutnumi; if (i+1)%3) cout ; else coutn; /赋值运算符重载CEight& CEight:operator=(CEight& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;deapth=

24、another_8num.deapth+1;return *this;CEight& CEight:operator=(int other_num9)for (int i=0;i9;i+)numi=other_numi;return *this;/相等关系运算符重载int CEight:operator=(CEight& another_8num)int match=1;for (int i=0;i9;i+)if(numi!=another_8num.numi) match=0; break;if (match=0) return 0;else return 1;int CEi

25、ght:operator=(int other_num9)int match=1;for (int i=0;i9;i+)if(numi!=other_numi)match=0; break;if (match=0)return 0;else return 1;int move_up(int num9) /空格向上移 int i;for (i=0;i9;i+)/找空格位置if (numi=0) break;if (i3) return 0;else /空格不在第一行时移动numi=numi-3;numi-3=0; return 1;int move_down(int num9) /空格向下移 i

26、nt i;for (i=0;i5) return 0;else/空格不在第三行时移动numi=numi+3;numi+3=0; return 1;int move_left(int num9) /空格向左移 int i;for (i=0;i9;i+) /找空格位置if (numi=0) break;if (i=0|i=3|i=6)return 0;else /空格不在第一列时移动numi=numi-1;numi-1=0; return 1;int move_right(int num9) /空格向右移 int i;for (i=0;i9;i+) /找空格位置if (numi=0) break;

27、if (i=2|i=5|i=8)return 0;else /空格不在第三列时移动numi=numi+1;numi+1=0;return 1;int icansolve(int num9,int target9) /判断可否解出int i,j;int count_num = 0;int count_target = 0;for (i=0;i9;i+)for (j=0;ji;j+) if(numjnumi&numj!=0) count_num+;if(targetjparent)if(*p=num) return 1;return 0;int main(void)int step=0;i

28、nt num9;int flag=0;/是否输入错误标志，1表示输入错误int bingo=0;/是否查找成功标志，1表示成功int i,j;coutPlease input the number(0 for the blank):n; /输入数据for (i=0;inumi;for(j=0;ji;j+)if(numi=numj)flag=1;if (numi8|flag=1)i-;coutIllegle number!tReinput!n;coutinput;if (input=y|input=Y)coutnPlease input the new target:n;for (i=0;ita

29、rgeti;for(j=0;ji;j+) if(targeti=targetj)flag=1;if (targeti8|flag=1)i-;coutIllegle number!tReinput!n“; CEight S(num),Target(target);S.parent=S.open_next=NULL;coutNow the initial numbers are:n; S.show();coutAnd the Target is:n; Target.show();if(!icansolve(num,target) /判断是否可解coutNo one can solve it!n;r

30、eturn 1;CEight *open_head=&S,*open_tos=&S,*new_8num; /BFS搜索while(open_head!=NULL&bingo!=1) if(*open_head=Target) bingo=1; break;for (int i=0;iget_numbers_to(num); bool bRec = false; switch(i) case 0: bRec = move_up(num); break; case 1: bRec = move_down(num); break; case 2: bRec = move_le

31、ft(num); break; case 3: bRec = move_right(num); break; if(bRec&!existed(num,open_head) new_8num=new CEight; new_8num-set_num(num); new_8num-parent=open_head; new_8num-open_next=NULL; open_tos-open_next=new_8num; open_tos=new_8num; open_head=open_head-open_next; /输出结果if(bingo=1)CEight *p;for (p=o

32、pen_head-parent;p!=NULL;p=p-parent)coutshow();step+;coutTotaly covered steps:stepn;elsecoutFail to find!;return 0;广搜的解法二：小结o 定义8数码结点类CEight，及一些普通的功能函数（如移动、是否有解、是否重复等）o 用链表表示队列，设置链表头指针open_head和尾指针open_toso 用遍历链表来查找是否有重复扩展结点n 较为低效o 通过链表运算来实现BFS用深度优先搜索求解8数码问题o 基本思想：优先深入遍历靠前的节点n 也可以通过链表实现，对上述算法中简单修改即可8

33、23416578234157682341650782413576823415768234165746用深度优先搜索求解8数码问题o 参考代码n 与前述BFS的代码为同一架构n 深度受限的情况下（如最大深度为20）：可能处理时间较长，且不一定能找到解度量问题求解的性能o完备性：当问题有解时，这个算法是否能够保证找到一个解o最优性：这个搜索策略是否能够找到最优解o时间复杂度：找到一个解需要花费多长时间o空间复杂度：在执行搜索的过程中需要多少内存广搜与深搜的比较o 广搜一般用于状态表示比较简单、求最优策略的问题n 优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，

34、还一定是路径最短的解。n 缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大o 深搜几乎可以用于任何问题n 只需要保存从起始状态到当前状态路径上的节点o 根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择49扩展问题：是否有更快的做法？o 双向广度优先搜索：从两个方向以广度优先的顺序同时扩展o A*：启发式搜索搜索50双向广度优先搜索(DBFS)o DBFS算法是对BFS算法的一种扩展。n BFS算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点n DBFS算法从两个方向以广度优先的顺序同时扩展，一个

35、是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。o 比较n DBFS算法相对于BFS算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！DBFS的框架(1)o 一、主控函数:void solve()1. 将起始节点放入队列q1,将目的节点放入队列q2；2. 当 两个队列都未空时，作如下循环： 1) 如果队列q1里的未处理节点比q2中的少（即tail0-head0 = tail1-head1时)；3. 如果队

36、列q1未空，循环扩展（expand()）q1直到为空；4. 如果队列q2未空，循环扩展（expand()）q2直到为空；DBFS的框架(2)o 二、扩展函数int expand(i) /其中i为队列的编号(表示q0或者q1) 取队列qi的头结点H； 对头节点H的每一个相邻节点adj，作如下循环： 1 如果adj已经在队列qi之前的某个位置出现，则 抛弃节点adj； 2 如果adj在队列qi中不存在函数 isduplicate(i) 1） 将adj放入队列qi； 2) 如果adj 在队列(q(1-i)，也就是另外一个 队列中出现函数 isintersect()； 输出 找到路径 ；DBFS的框架

37、(3)o 三、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数：int isintersect(i,j) /i为队列编号，j为当前节点在队列中的指针 遍历队列,判断是否存在/【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)】DBFS参考代码o 见附件o 进一步提高查找效率，采用hash函数优化线性查找n 见附件A*算法o 针对八数码问题，提出了人工智能史上很有名的A*算法(启发式搜索算法)n 广度优先算法：当目标的深度较深时，产生很多冗余节点，空间消耗很大n 有限深度优先算法：在时间或空间复杂度上均没有明显的优势，但如果目标深度较深而且

38、路径选择得当的话，可以较快地得到解答；当问题复杂时时间消耗很多n A*算法：可以消耗较少的空间解决问题，但是由于每次选择均需要寻找估价函数最小的节点，因此当深度增加相应的节点数目增加时，A*算法在时间上并不占优势。然而，A*算法总可以在有限的时间内得到问题的解。56A*算法的基本思想o A*算法基本上与BFS算法相同，但是在扩展出一结点后，要根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。o 估价函数： f(n) = g(n) + h(n) 这里f(n)是估价函数，g(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h(n)是n到目标的最短路经的启发值。

39、o 由于这个f(n)其实是无法预先知道的，所以实际上使用“不在位”数和当前层数之和A*算法的基本步骤o建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 o取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 o检查扩展的新结点是否与队列中的结点重复l若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；l若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 o如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后

40、待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针o如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。#include iostream using namespace std;static int target9=1,2,3,4,5,6,7,8,0;class CEightprivate:int num9; int deapth;int not_in_position_num; int eva_function;public:CEight* parent; CEight* open_next;CEight* leaf_pre;CEigh

41、t(int init_num9);CEight(void);void get_numbers_to(int other_num9);int get_deapth(void); void cul_para(void); int get_nipn(void); int get_evafun(void);void set_num(int other_num9);void show(void);CEight& operator=(CEight&);CEight& operator=(int other_num9);/修改int operator=(CEight&);int operator=(int other_num9);int CEight:get_nipn(void) return not_in_position_num;int CEight: get_evafun(void)return eva_function;void CEight:cul_para(void)int i;int temp_nipn=0;for (i=0;iparent=NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_n