搜索-BFS

SEARCHINGSTRATEGIESACM/ICPC之搜索篇2020/4/172搜索概论搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。本节目标：希望同学们对于任意一个问题，1.很快建立状态空间2.提出一个合理算法3.简单估计时空性能2020/4/173搜索分类盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。2020/4/174搜索算法盲目搜索：1.广度优先搜索（BreadthFirstSearch）2.深度优先搜索（DepthFirstSearch）3.纯随机搜索、重复式搜索、迭代加深搜索、迭代加宽搜索、柱型搜索启发式搜索：1.A*算法2.IDA*算法2020/4/175状态空间明确以下概念：状态：问题在某一时刻进展状况的数学描述。状态转移：问题从一种状态到另一种或几种状态的操作。状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。2020/4/176过河问题某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?2020/4/177过河问题（con1）状态：建立四元组（人，狗，鸡，米）。用0表示在左岸，1表示在右岸。起始状态(0,0,0,0)，终止状态(1,1,1,1)状态转移规则：(a,b,c,d)→(1-a,1-b,c,d)（当a=b）→(1-a,b,1-c,d)（当a=c）→(1-a,b,c,1-d)（当a=d）→(1-a,b,c,d)约束：(a,b,c,d)中，当a≠b时b≠c；当a≠c时c≠d2020/4/178过河问题（con2）搜索：(0,0,0,0)→(1,1,0,0)→(1,0,1,0)→(0,0,1,0)→(1,0,1,1)→(1,0,0,1)→(1,1,1,0)→(1,0,0,0)2020/4/179过河问题（con3）搜索：→(1,0,1,1)→(0,0,0,1)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,0,1,1)→(1,1,1,0)→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,1,0,0)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,1,1,0)2020/4/1710过河问题（con4）搜索在“图”中进行，但图不需要事先建立（“隐式图”）。搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。搜索树的结点个数、分枝数、深度，决定着搜索的效率。2020/4/1711过河问题（con5）2020/4/1712过河问题（con6）普通状态可以用4个整数表示压缩状态用4个bit表示(char型有8个bit，足够用)。用广度优先(BFS,BreathFirstSearch)或用深度优先(DFS,DepthFirstSearch)2020/4/1713BFS+DFS入门顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方……深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。2020/4/1714BFS思想1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v2…2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。//搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E)2020/4/1715BFS思想（cont.）树、图的BFS演示01234859671002145362020/4/1716BFS程序基本结构定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;这个结构是普遍适用的。任何非递归的BFS程序都能套进去2020/4/1717BFS演示无向图如下，边权均为1，求V1到V3的最短路径V3V2V4V1V6V52020/4/1718定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V1队列结点记录两个信息1：顶点编号2：步数2020/4/1719定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V12020/4/1720定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V1v102020/4/1721定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V1v10V1不是终点2020/4/1722定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v102020/4/1723定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v612020/4/1724定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v212020/4/1725定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V2不是终点v212020/4/1726定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v212020/4/1727定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v322020/4/1728定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v412020/4/1729定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是终点2020/4/1730定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v412020/4/1731定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v512020/4/1732定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v612020/4/1733定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v322020/4/1734定义一个队列;起始点加入队列;while(队列不空){取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添到队尾;}若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是终点，结束搜索，输出22020/4/1735例1KnightMoves象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？输入：a1h8输出：Togetfroma1toh8takes6knightmoves.abcdefgh12345678h8a12020/4/1736跳马规则abcdefgh12345678在2×3的矩形里：2020/4/1737例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。Togetfroma1toe4takes3knightmoves.abcdefgh12345678033213223123322333233333332333322020/4/1738boolin(inta,intb){if(a0&&a=8&&b0&&b=8)returntrue;returnfalse;}intbfs(){intcol,row,i;while(!qq.empty()){col=qq.front();qq.pop();row=qq.front();qq.pop();ans=qq.front();qq.pop();if(col==a[2]&&row==a[3])returnans;for(i=0;i8;i++){if(in(row+dir[i].x,col+dir[i].y)&&!mp[row+dir[i].x][col+dir[i].y]){qq.push(col+dir[i].y);qq.push(row+dir[i].x);qq.push(ans+1);mp[row+dir[i].x][col+dir[i].y]=true;}}}}#includeiostream#includequeueusingnamespacestd;structxxx{intx,y;};xxxdir[8]={{-2,1},{-2,-1},{-1,-2},