《第18讲 广度优先搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《第18讲 广度优先搜索ppt课件.ppt（67页珍藏版）》请在三一办公上搜索。
1、程序设计实习,第十八讲 广度优先搜索,内容提要,广度优先搜索的基本思想POJ1077八数码问题广搜双向广搜(扩展，不要求)A*(扩展，不要求)小结：影响搜索效率的因素,2,广度优先搜索,广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。假设有两个表：Open表存放待处理节点，Closed表存放处理完节点Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。,广度优先搜索,两个状态的集合:未处
2、理完的状态:已处理的状态从中选择被演化状态的原则：离初态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)若节点
3、n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,例题：POJ1077八数码问题,八数码问题是人工智能中的经典问题POJ1077八数码问题：经典搜索问题有一个3*3的棋盘，其中有0-8共9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态1 2 34 5 67 8 0的步数最少的解？,7,例题：POJ1077八数码问题,状态空间,8,广度优先搜索,广度优先搜索（bfs）优先扩展浅层节点，逐渐深入,第一层,第二层,第三层,9,广度优先搜索,广度优先搜索用队列保存待扩展的节点，从队首队取出节
4、点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）,10,广度优先搜索,广度优先搜索的代码框架,BFS()初始化队列while(队列不为空且未找到目标节点)取队首节点扩展，并将扩展出的节点放入队尾；必要时要记住每个节点的父节点；,11,关键问题：判重,判重新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑如何判重？,重复?,12,关键问题：判重,需要考虑的问题状态数目巨大，如何存储？怎样才能较快的找到重复节点？,时间,空间,13,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。（228
5、 99=387,420,489 229）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8+1个字节 48,427,562字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8),14,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相
6、转换函数。,15,判重,合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别,方案二：为节点编号把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个节点判重用的标志数组只需要362,880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。,16,判重,时间与空间的权衡对于状态数较小的问题，可以用最直接的方式编码以空间换时间对于状态数太大的问题，需要利用好的编码方法以时间换空间具体问题具体分析,17,输入数据：2
7、3 4 1 5 x 7 6 8输出结果：ullddrurdllurdruldr,2 3 4 1 5 7 6 8,输入数据代表：,移动序列中u 表示使空格上移d 表示使空格下移r 表示使空格右移l 表示使空格左移,1 2 3 4 5 6 7 8,输出数据是一个移动序列，使得移动后结果变成,用广搜解决八数码问题,18,八数码例子程序,采用方案1的非递归方案：数据结构用一个九进制字符串表示一个节点，其中有且仅有一个0（表示空格）-因此若九进制串中没有0，则0一定是在最高位设一个48427562位字符型标志位序列数组szFlag，标识每个状态是否已扩展设一个队列MyQueue存放搜索过程中的可能状态，
8、根据问题定义，状态总数362880。考虑到搜索过程中可能存在的重复状态，其大小设为400000。为简化计算，设置与MyQueue同样大小的数组anFather存放父节点指针、数组szMoves存放从父节点到当前节点的移动步骤设置一个结果队列，为防止溢出，设置与MyQueue同样大小,19,八数码例子程序,采用方案1的非递归方案：关键处理逻辑Main程序1.将输入的原始字符串变为九进制字符串;2.用BFS过程看是否可以达到目标状态;3.若能达到，通过anFather数组找到成功的状态序列;4.根据数组szMoves找到相应的移动步骤，并输出.BFS过程输入：初始状态 输出：成功/失败；若成功，a
9、nFather、szMoves,20,八数码例子程序,采用方案1的非递归方案：关键处理逻辑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
10、 Flags;/节点是否扩展的标记char szResult400000;/结果char szMoves400000;/移动步骤：u/d/r/l int anFather400000;/父节点指针int MyQueue400000;/状态队列，状态总数362880int nQHead;int nQTail;char sz4Moves=udrl;/四种动作,八数码例子程序,22,int NineToTen(char*s)/九进制字符串转十进制int nResult=0;for(int i=0;si;i+)nResult*=9;nResult+=si-0;return nResult;,23,in
11、t 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;,24,int NewStatus(int nStatus,char cMove)/求从nStatus经过 cMove 移动后得到的新状态。若移动不可行则返回-1char szTmp20;int nZeroPos=TenToNine(nStatus
12、,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(nZeroPos%3=2)return-1;/空格在第三列else szTmpnZeroPos=szTmpnZeroPos+1;s
13、zTmpnZeroPos+1=0;break;return NineToTen(szTmp);,25,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种移动nNewStatus=NewStatus(nStatus,sz4Movesi);if(nNewStatus=-
14、1)continue;/不可移，试下一种if(FlagsnNewStatus)continue;/如果扩展标记已经存在，则不能入队Flags.set(nNewStatus,true);/设上已扩展标记MyQueuenQTail=nNewStatus;/新节点入队列 anFathernQTail=nQHead;/记录父节点/记录本节点是由父节点经什么动作而来szMovesnQTail=sz4Movesi;nQTail+;nQHead+;return false;,26,int main()nGoalStatus=NineToTen(123456780);Flags.reset();char sz
15、Line50;char szLine220;cin.getline(szLine,48);int i,j;/将输入的原始字符串变为九进制字符串for(i=0,j=0;szLinei;i+)if(szLinei!=)if(szLinei=x)szLine2j+=0;else szLine2j+=szLinei;szLine2j=0;if(Bfs(NineToTen(szLine2)int nMoves=0;int nPos=nQHead;do/通过anFather数组找到成功的状态序列，输出相应步骤szResultnMoves+=szMovesnPos;nPos=anFathernPos;whi
16、le(nPos);for(int i=nMoves-1;i=0;i-)cout szResulti;elsecout unsolvable endl;return 0;,27,问题,前述程序中，是否有状态被重复扩展？初始状态。为避免此重复，应在BFS初始化时对初始状态进行置位前述程序中，8数码问题的有解性判定如果所有结点都扩展完还没有达到目标状态，则问题无解，失败退出是否有更节省存储空间的做法，例如可以不用几个大数组？一种可能方案：使用2个链表分别存队列和结果,28,广搜的解法二：链表表示,基本思想：定义8数码结点类CEight,它有两个指针open_next和parent，分别指向BFS扩展
17、结点的下一个open节点和父结点（若当前结点为目标结点，通过parent可以得到解路径）不需要设置标志位序列数组szFlag用链表来表示状态队列MyQueue其他要求目标结点可以支持重新设定，这样可以用于计算任意两个结点间的距离输出结果将解路径打印出来,八数码问题：任意两结点间路径,实现细节(1),8数码结点类CEight=：两对象赋值，或用数组给对象赋值=：两对象是否相等，或对象和一用数组存储的结点是否相等普通函数四类移动操作move_left/right/up/down判断有无重复existed：链表遍历判定是否有解icansolve,八数码问题有解性的判定,八数码问题的一个状态实际上是0
18、9的一个排列，对于任意给定的初始状态和目标，不一定有解，即从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。如果一个数字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=9 9是奇数，所以是奇排列。因此，可以在运行程序前检查初始状态和目标状态的奇偶性是否相同，相同则问题可解，应当能
19、搜索到路径。否则无解。,实现细节(2),广搜过程让链表头指针open_head和尾指针open_tos指向初始节点S；while(open_head不为空且找到标志为假)if(*open_head=Target)找到标志为真;break;Repeat 四种动作 分别执行一种动作；if(动作执行成功,#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;/父指针CEi
20、ght*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,注意：本解法与POJ要求不完全相同，但很容易修改和移植,CEight:CEight(int init_num9)for(int i=0;i9;i+)numi=i
21、nit_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_num9)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
22、 coutn;/赋值运算符重载CEight,/相等关系运算符重载int CEight:operator=(CEight,int move_up(int num9)/空格向上移 int 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
23、;int move_right(int num9)/空格向右移 int i;for(i=0;i9;i+)/找空格位置if(numi=0)break;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;iparent)if(*p=num)return 1;return 0;,int main(void)int step=0;i
24、nt num9;int flag=0;/是否输入错误标志，1表示输入错误int bingo=0;/是否查找成功标志，1表示成功int i,j;coutnumi;for(j=0;j8|flag=1)i-;coutIllegle number!tReinput!n;,coutinput;if(input=y|input=Y)couttargeti;for(j=0;j8|flag=1)i-;coutIllegle number!tReinput!n“;CEight S(num),Target(target);S.parent=S.open_next=NULL;coutNow the initial
25、numbers are:n;S.show();coutAnd the Target is:n;Target.show();if(!icansolve(num,target)/判断是否可解coutNo one can solve it!n;return 1;,CEight*open_head=,/输出结果if(bingo=1)CEight*p;for(p=open_head-parent;p!=NULL;p=p-parent)coutshow();step+;coutTotaly covered steps:stepn;elsecoutFail to find!;return 0;,广搜的解法二
26、：小结,定义8数码结点类CEight，及一些普通的功能函数（如移动、是否有解、是否重复等）用链表表示队列，设置链表头指针open_head和尾指针open_tos用遍历链表来查找是否有重复扩展结点较为低效通过链表运算来实现BFS,用深度优先搜索求解8数码问题,基本思想：优先深入遍历靠前的节点也可以通过链表实现，对上述算法中简单修改即可,46,用深度优先搜索求解8数码问题,参考代码与前述BFS的代码为同一架构深度受限的情况下（如最大深度为20）：可能处理时间较长，且不一定能找到解,度量问题求解的性能,完备性：当问题有解时，这个算法是否能够保证找到一个解最优性：这个搜索策略是否能够找到最优解时间复
27、杂度：找到一个解需要花费多长时间空间复杂度：在执行搜索的过程中需要多少内存,广搜与深搜的比较,广搜一般用于状态表示比较简单、求最优策略的问题优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大深搜几乎可以用于任何问题只需要保存从起始状态到当前状态路径上的节点根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择,49,扩展问题：是否有更快的做法？,双向广度优先搜索：从两个方向以广度优先的顺序同时扩展A*：启
28、发式搜索搜索,50,双向广度优先搜索(DBFS),DBFS算法是对BFS算法的一种扩展。BFS算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点DBFS算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。比较DBFS算法相对于BFS算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！,DBFS的框架(1),一、主控函数:void solve()1.将起始节点放入
29、队列q1,将目的节点放入队列q2；2.当 两个队列都未空时，作如下循环：1)如果队列q1里的未处理节点比q2中的少（即tail0-head0=tail1-head1时)；3.如果队列q1未空，循环扩展（expand()）q1直到为空；4.如果队列q2未空，循环扩展（expand()）q2直到为空；,DBFS的框架(2),二、扩展函数int expand(i)/其中i为队列的编号(表示q0或者q1)取队列qi的头结点H；对头节点H的每一个相邻节点adj，作如下循环：1 如果adj已经在队列qi之前的某个位置出现，则 抛弃节点adj；2 如果adj在队列qi中不存在函数 isduplicate(i
30、)1）将adj放入队列qi；2)如果adj 在队列(q(1-i)，也就是另外一个 队列中出现函数 isintersect()；输出 找到路径；,DBFS的框架(3),三、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数：int isintersect(i,j)/i为队列编号，j为当前节点在队列中的指针遍历队列,判断是否存在/【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)】,DBFS参考代码,见附件进一步提高查找效率，采用hash函数优化线性查找见附件,A*算法,针对八数码问题，提出了人工智能史上很有名的A*算法(启发式搜索算法)广度优
31、先算法：当目标的深度较深时，产生很多冗余节点，空间消耗很大有限深度优先算法：在时间或空间复杂度上均没有明显的优势，但如果目标深度较深而且路径选择得当的话，可以较快地得到解答；当问题复杂时时间消耗很多A*算法：可以消耗较少的空间解决问题，但是由于每次选择均需要寻找估价函数最小的节点，因此当深度增加相应的节点数目增加时，A*算法在时间上并不占优势。然而，A*算法总可以在有限的时间内得到问题的解。,56,A*算法的基本思想,A*算法基本上与BFS算法相同，但是在扩展出一结点后，要根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。估价函数：f(n)=g(n)+h(n)这里f
32、(n)是估价函数，g(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h(n)是n到目标的最短路经的启发值。由于这个f(n)其实是无法预先知道的，所以实际上使用“不在位”数和当前层数之和,A*算法的基本步骤,建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。检查扩展的新结点是否与队列中的结点重复若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。
33、跳至第五步。如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。,#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*p
34、arent;CEight*open_next;CEight*leaf_pre;CEight(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,int CEight:get_nipn(void)return not_in_position_num;int C
35、Eight: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_num+deapth;CEight,/寻找估价函数最小的叶子节点CEight*find_OK_leaf(CEight*start)CEight*p,*OK;p=OK=start;int min=start-get_evafun();for
36、(p=start;p!=NULL;p=p-leaf_next)if(minp-get_evafun()OK=p;min=p-get_evafun();return OK;,/主函数开始int main(void)/和 BFS前面一样 CEight S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();coutNow the initial numbers are:n;S.show();coutAnd the Target is:n;Target.show();if(!icansolve(num,targe
37、t)coutNo one can solve it!n;return 1;,CEight*OK_leaf=,if(bRec/和 BFS后面类似,A*参考程序,完整A*参考程序见附件,BFS vs.DBFS vs.A*,BFS算法只能适用于到达目标结点步数较少的情况，如果步数超过15步，运行时间太长。对于随机生成的同一个可解状态，BFS算法最慢，A*算法较快。但在15步以内，DBFS算法与A*算法相差时间不大，超过15步后，随步数增加，A*算法的优势就逐渐明显，A*算法要比DBFS算法快5倍以上，并随步数增大而增大。到25步以上，DBFS同样因运行时间过长而失去价值。一般来说，解答的移动步数每增加1，程序运行时间就要增加5倍以上。由于八数码问题本身的特点，需要检查的节点随步数增大呈指数形式增加，即使用A*算法，也难解决移动步数更多的问题。,小结：影响搜索效率的因素,影响搜索效率的因素搜索对象(枚举什么）搜索顺序（先枚举什么，后枚举什么）BFS：广度优先DFS：深度优先A*：估价函数最小优先剪枝(及早判断出不符合要求的情况）,67,
