第18讲-广度优先搜索

程序设计实习第十八讲广度优先搜索内容提要广度优先搜索的基本思想POJ1077八数码问题广搜双向广搜(扩展，不要求)A*(扩展，不要求)小结：影响搜索效率的因素2广度优先搜索广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。假设有两个表：Open表存放待处理节点，Closed表存放处理完节点Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。广度优先搜索两个状态的集合:未处理完的状态:已处理的状态从中选择被演化状态的原则：离初态S0距离最近的状态sS0到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的步数最少的解？12345678823146577例题：POJ1077八数码问题状态空间8234165782341576823416578241357682341576823416578广度优先搜索广度优先搜索（bfs）优先扩展浅层节点，逐渐深入第一层第二层第三层8234165782341576823416578241357682341576823416579广度优先搜索广度优先搜索用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）823416578234157682413576823415768234165710广度优先搜索广度优先搜索的代码框架BFS(){初始化队列while(队列不为空且未找到目标节点){取队首节点扩展，并将扩展出的节点放入队尾；必要时要记住每个节点的父节点；}}11关键问题：判重判重新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑如何判重？重复?823416578234157682341650782413576823415768234165712关键问题：判重需要考虑的问题状态数目巨大，如何存储？怎样才能较快的找到重复节点？时间空间13判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。（22899=387,420,489229）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8+1个字节48,427,562字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8)14判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。15判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案二：为节点编号把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个节点判重用的标志数组只需要362,880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。16判重时间与空间的权衡对于状态数较小的问题，可以用最直接的方式编码以空间换时间对于状态数太大的问题，需要利用好的编码方法以时间换空间具体问题具体分析17输入数据：23415x768输出结果：ullddrurdllurdruldr23415768输入数据代表：移动序列中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、szMoves20八数码例子程序采用方案1的非递归方案：关键处理逻辑BFS中的关键问题：1）如何进行状态扩展？2）状态中0的位置与cMove动作间的关系？3）如何计算求从nStatus经过cMove移动后得到的新状态（定义为函数NewStatus）？4）如何判断扩展标记已经存在？5）对未扩展状态，如何置已扩展标记(定义为函数SetBit)？6）字符串形式的9进制数到其整型值的互相转换函数（定义为NineToTen和TenToNine）21#includeiostream#includebitsetusingnamespacestd;intnGoalStatus;//目标状态bitset387420498Flags;//节点是否扩展的标记charszResult[400000];//结果charszMoves[400000];//移动步骤：u/d/r/lintanFather[400000];//父节点指针intMyQueue[400000];//状态队列，状态总数362880intnQHead;intnQTail;charsz4Moves[]=udrl;//四种动作八数码例子程序22intNineToTen(char*s){//九进制字符串转十进制intnResult=0;for(inti=0;s[i];i++){nResult*=9;nResult+=s[i]-'0';}returnnResult;}23intTenToNine(intn,char*s){//十进制数转九进制字符串。可能有前导0，返回0的位置intnZeroPos;intnBase=1;intj=0;while(nBase=n)/*从高位开始的进制转换*/nBase*=9;nBase/=9;do{s[j]=n/nBase+'0';if(s[j]=='0')nZeroPos=j;j++;n%=nBase;nBase/=9;}while(nBase=1);s[j]=0;//串结束符//判断是否要加前导0，此时第0位即为0if(j9){for(inti=j+1;i0;i--)s[i]=s[i-1];s[0]='0';return0;}returnnZeroPos;}24intNewStatus(intnStatus,charcMove){//求从nStatus经过cMove移动后得到的新状态。若移动不可行则返回-1charszTmp[20];intnZeroPos=TenToNine(nStatus,szTmp);//返回空格的位置switch(cMove){case'u':if(nZeroPos-30)return-1;//空格在第一行else{szTmp[nZeroPos]=szTmp[nZeroPos-3];szTmp[nZeroPos-3]='0';}break;case'd':if(nZeroPos+38)return-1;//空格在第三行else{szTmp[nZeroPos]=szTmp[nZeroPos+3];szTmp[nZeroPos+3]='0';}break;case'l':if(nZeroPos%3==0)return-1;//空格在第一列else{szTmp[nZeroPos]=szTmp[nZeroPos-1];szTmp[nZeroPos-1]='0';}break;case'r':if(nZeroPos%3==2)return-1;//空格在第三列else{szTmp[nZeroPos]=szTmp[nZeroPos+1];szTmp[nZeroPos+1]='0';}break;}returnNineToTen(szTmp);}25boolBfs(intnStatus){intnNewStatus;nQHead=0;nQTail=1;MyQueue[nQHead]=nStatus;while(nQHead!=nQTail){//队列不为空nStatus=MyQueue[nQHead];if(nStatus==nGoalStatus)//找到目标状态returntrue;for(inti=0;i4;i++){//尝试4种移动nNewStatus=NewStatus(nStatus,sz4Moves[i]);if(nNewStatus==-1)continue;//不可移，试下一种if(Flags[nNewStatus])continue;//如果扩展标记已经存在，则不能入队Flags.set(nNewStatus,true);//设上已扩展标记MyQueue[nQTail]=nNewStatus;//新节点入队列anFather[nQTail]=nQHead;//记录父节点//记录本节点是由父节点经什么动作而来szMoves[nQTail]=sz4Moves[i];nQTail++;}nQHead++;}returnfalse;}26intmain(){nGoalStatus=NineToTen(123456780);Flags.reset();charszLine[50];charszLine2[20];cin.getline(szLine,48);inti,j;//将输入的原始字符串变为九进制字符串for(i=0,j=0;szLine[i];i++){if(szLine[i]!=''){if(szLine[i]=='x')szLine2[j++]='0';elseszLine2[j++]=szLine[i];}}szLine2[j]=0;if(Bfs(NineToTen(szLine2))){intnMoves=0;intnPos=nQHead;do{//通过anFather数