程序设计实习第十八讲广度优先搜索内容提要广度优先搜索的基本思想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的步数最少的解?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数