广度优先搜索

程序设计实习,第十八讲广度优先搜索,内容提要,广度优先搜索的基本思想POJ1077八数码问题广搜双向广搜(扩展，不要求)A*(扩展，不要求)小结：影响搜索效率的因素,2,广度优先搜索,广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。假设有两个表：Open表存放待处理节点，Closed表存放处理完节点Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。,广度优先搜索,两个状态的集合:未处理完的状态:已处理的状态从中选择被演化状态的原则：离初态S0距离最近的状态sS0到s的距离：从S0到达s使用的动作数量实现方法：用queue表示每次取queue头部的状态演化每次演化出的状态s若不属于，则s将压入queue的尾部,深搜vs.广搜,深搜1-2-4-8-5-6-3-7广搜1-2-3-4-5-6-7-8,广搜算法,广度优先搜索算法如下：（用QUEUE）(1)把初始节点S0放入Open表中；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,例题：POJ1077八数码问题,八数码问题是人工智能中的经典问题POJ1077八数码问题：经典搜索问题有一个3*3的棋盘，其中有0-8共9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态123456780的步数最少的解？,7,例题：POJ1077八数码问题,状态空间,8,广度优先搜索,广度优先搜索（bfs）优先扩展浅层节点，逐渐深入,第一层,第二层,第三层,9,用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）,10,广度优先搜索,广度优先搜索的代码框架,VoidBFS()初始化队列while(队列不为空且未找到目标节点)取队首节点扩展，并将扩展出的节点放入队尾；必要时要记住每个节点的父节点；,11,关键问题：判重,判重新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑如何判重？,重复?,12,关键问题：判重,需要考虑的问题状态数目巨大，如何存储？怎样才能较快的找到重复节点？,时间,空间,13,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。（22899=387,420,489229）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8+1个字节48,427,562字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8),14,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。,15,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案二：为节点编号把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个节点判重用的标志数组只需要362,880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。,16,判重,时间与空间的权衡对于状态数较小的问题，可以用最直接的方式编码以空间换时间对于状态数太大的问题，需要利用好的编码方法以时间换空间具体问题具体分析,17,输入数据：23415x768输出结果：ullddrurdllurdruldr,23415768,输入数据代表：,移动序列中u表示使空格上移d表示使空格下移r表示使空格右移l表示使空格左移,12345678,输出数据是一个移动序列，使得移动后结果变成,用广搜解决八数码问题,18,八数码例子程序,采用方案1的非递归方案：数据结构用一个九进制字符串表示一个节点，其中有且仅有一个0（表示空格）-因此若九进制串中没有0，则0一定是在最高位设一个48427562位字符型标志位序列数组szFlag，标识每个状态是否已扩展设一个队列MyQueue存放搜索过程中的可能状态，根据问题定义，状态总数362880。考虑到搜索过程中可能存在的重复状态，其大小设为400000。为简化计算，设置与MyQueue同样大小的数组anFather存放父节点指针、数组szMoves存放从父节点到当前节点的移动步骤设置一个结果队列，为防止溢出，设置与MyQueue同样大小,19,八数码例子程序,采用方案1的非递归方案：关键处理逻辑Main程序1.将输入的原始字符串变为九进制字符串;2.用BFS过程看是否可以达到目标状态;3.若能达到，通过anFather数组找到成功的状态序列;4.根据数组szMoves找到相应的移动步骤，并输出.BFS过程输入：初始状态输出：成功/失败；若成功，anFather、szMoves,20,八数码例子程序,采用方案1的非递归方案：关键处理逻辑BFS中的关键问题：1）如何进行状态扩展？2）状态中0的位置与cMove动作间的关系？3）如何计算求从nStatus经过cMove移动后得到的新状态（定义为函数NewStatus）？4）如何判断扩展标记已经存在？5）对未扩展状态，如何置已扩展标记(定义为函数SetBit)？6）字符串形式的9进制数到其整型值的互相转换函数（定义为NineToTen和TenToNine）,21,#include#includeusingnamespacestd;intnGoalStatus;/目标状态bitsetFlags;/节点是否扩展的标记charszResult400000;/结果charszMoves400000;/移动步骤：u/d/r/lintanFather400000;/父节点指针intMyQueue400000;/状态队列，状态总数362880intnQHead;intnQTail;charsz4Moves=udrl;/四种动作,八数码例子程序,22,intNineToTen(char*s)/九进制字符串转十进制intnResult=0;for(inti=0;si;i+)nResult*=9;nResult+=si-0;returnnResult;,23,intTenToNine(intn,char*s)/十进制数转九进制字符串。可能有前导0，返回0的位置intnZeroPos;intnBase=1;intj=0;while(nBase=1);sj=0;/串结束符/判断是否要加前导0，此时第0位即为0if(j0;i-)si=si-1;s0=0;return0;returnnZeroPos;,24,intNewStatus(intnStatus,charcMove)/求从nStatus经过cMove移动后得到的新状态。若移动不可行则返回-1charszTmp20;intnZeroPos=TenToNine(nStatus,szTmp);/返回空格的位置switch(cMove)caseu:if(nZeroPos-38)return-1;/空格在第三行elseszTmpnZeroPos=szTmpnZeroPos+3;szTmpnZeroPos+3=0;break;casel:if(nZeroPos%3=0)return-1;/空格在第一列elseszTmpnZeroPos=szTmpnZeroPos-1;szTmpnZeroPos-1=0;break;caser:if(nZeroPos%3=2)return-1;/空格在第三列elseszTmpnZeroPos=szTmpnZeroPos+1;szTmpnZeroPos+1=0;break;returnNineToTen(szTmp);,25,boolBfs(intnStatus)intnNewStatus;nQHead=0;nQTail=1;MyQueuenQHead=nStatus;while(nQHead!=nQTail)/队列不为空nStatus=MyQueuenQHead;if(nStatus=nGoalStatus)/找到目标状态returntrue;for(inti=0;i=0;i-)coutszResulti;elsecoutunsolvableendl;return0;,27,问题,前述程序中，是否有状态被重复扩展？初始状态。为避免此重复，应在BFS初始化时对初始状态进行置位前述程序中，8数码问题的有解性判定如果所有结点都扩展完还没有达到目标状态，则问题无解，失败退出是否有更节省存储空间的做法，例如可以不用几个大数组？一种可能方案：使用2个链表分别存队列和结果,28,广搜的解法二：链表表示,基本思想：定义8数码结点类CEight,它有两个指针open_next和parent，分别指向BFS扩展结点的下一个open节点和父结点（若当前结点为目标结点，通过parent可以得到解路径）不需要设置标志位序列数组szFlag用链表来表示状态队列MyQueue其他要求目标结点可以支持重新设定，这样可以用于计算任意两个结点间的距离输出结果将解路径打印出来,八数码问题：任意两结点间路径,实现细节(1),8数码结点类CEight=：两对象赋值，或用数组给对象赋值=：两对象是否相等，或对象和一用数组存储的结点是否相等普通函数四类移动操作move_left/right/up/down判断有无重复existed：链表遍历判定是否有解icansolve,八数码问题有解性的判定,八数码问题的一个状态实际上是09的一个排列，对于任意给定的初始状态和目标，不一定有解，即从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。如果一个数字08的随机排列，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=(F(X)，如果Y为奇数则称该排列是奇排列，如果Y为偶数则称该排列是偶排列。871526340排列的Y=0+0+0+1+1+3+2+3+0=10，10是偶数，所以是偶排列。871625340排列的Y=0+0+0+1+1+2+2+3+0=99是奇数，所以是奇排列。因此，可以在运行程序前检查初始状态和目标状态的奇偶性是否相同，相同则问题可解，应当能搜索到路径。否则无解。,实现细节(2),广搜过程让链表头指针open_head和尾指针open_tos指向初始节点S；while(open_head不为空且找到标志为假)if(*open_head=Target)找到标志为真;break;Repeat四种动作分别执行一种动作；if(动作执行成功,#includeiostreamusingnamespacestd;staticinttarget9=1,2,3,4,5,6,7,8,0;classCEightprivate:intnum9;/结点数组intdeapth;/深度public:CEight*parent;/父指针CEight*open_next;/扩展指针CEight(intinit_num9);/用数组构造对象CEight(void);/构造函数，使用缺省初始化intget_deapth(void);/取深度voidget_numbers_to(intother_num9);/将数序列拷贝到另一数组voidset_num(intother_num9);/将另一数组的数序列设置对象voidshow(void);/输出结果CEight,注意：本解法与POJ要求不完全相同，但很容易修改和移植,CEight:CEight(intinit_num9)for(inti=0;i9;i+)numi=init_numi;CEight:CEight()for(inti=0;i9;i+)numi=i;intCEight:get_deapth(void)returndeapth;voidCEight:get_numbers_to(intother_num9)for(inti=0;i9;i+)other_numi=numi;voidCEight:set_num(intother_num9)for(inti=0;i9;i+)numi=other_numi;,voidCEight:show()for(inti=0;i9;i+)coutnumi;if(i+1)%3)cout;elsecoutn;/赋值运算符重载CEight,/相等关系运算符重载intCEight:operator=(CEight,intmove_up(intnum9)/空格向上移inti;for(i=0;i5)return0;else/空格不在第三行时移动numi=numi+3;numi+3=0;return1;,intmove_left(intnum9)/空格向左移inti;for(i=0;i9;i+)/找空格位置if(numi=0)break;if(i=0|i=3|i=6)return0;else/空格不在第一列时移动numi=numi-1;numi-1=0;return1;intmove_right(intnum9)/空格向右移inti;for(i=0;inumi;for(j=0;j8|flag=1)i-;couttargeti;for(j=0;j8|flag=1)i-;coutIlleglenumber!tReinput!n“;CEightS(num),Target(target);S.parent=S.open_next=NULL;coutNowtheinitialnumbersare:n;S.show();coutAndtheTargetis:n;Target.show();if(!icansolve(num,target)/判断是否可解coutparent)coutshow();step+;coutTotalycoveredsteps:stepn;elsecoutdeapth+1;eva_function=not_in_position_num+deapth;CEight,/寻找估价函数最小的叶子节点CEight*find_OK_leaf(CEight*start)CEight*p,*OK;p=OK=start;intmin=start-get_evafun();for(p=start;p!=NULL;p=p-leaf_next)if(minp-get_evafun