广度优先搜索Pascal.ppt

在广度优先搜索过程中，广度优先搜索算法(也称为广度优先搜索)是最简单的图搜索算法之一。该算法也是许多重要图形算法的原型。迪杰斯特拉的单源最短路径算法和普里姆的最小生成树算法都采用了宽度优先搜索的思想。广度优先搜索的核心思想是：从初始节点开始，应用算子生成第一级节点，并检查目标节点是否在这些后续节点中。如果没有，则使用生产规则将所有一级节点逐一展开，得到二级节点，并逐一检查二级节点是否包含目标节点。如果没有，那么使用操作符一个接一个地展开第二层中的所有节点依次展开并检查，直到找到目标节点。也就是1。从图中的顶点V0开始，首先访问V0；2.访问所有顶点V1，V2，Vt邻近V0。(3)顺序访问邻近V2 V1的所有未访问的顶点，和Vt。4.沿着这条路径，直到所有顶点都被访问过。这种搜索顺序反映了沿层次水平扩展的趋势，因此被称为广度优先搜索。广度优先搜索算法描述：ProgramBfs；初始化时，初始状态存储在队列中；head :=0；尾部指针尾部：=1；重复指针头向后移动一位，指向要扩展的节点；ForI=1 to macxdo/max是子节点的常规数量。beginif子节点满足条件。thenbegintail指针递增1，新节点存储在列的末尾。如果新节点与原始节点重复，则删除该节点(取消队列，尾部减1)，否则如果新节点是目标节点，则输出并退出；结束；结束；直到(头=尾)；/队列为空，广度优先搜索注意事项：1。对于生成的每个子节点，必须提供指向其父节点的指针。当解决方案出现时，通过反向跟踪找到从根节点到目标节点的路径。当然，不需要输出路径，所以不需要记住父亲。2.生成的节点应该与所有以前生成的节点进行比较，以避免重复节点、浪费时间和可能陷入死循环。3.如果目标节点的深度与“成本”(例如路径长度)成正比，那么找到的第一个解决方案就是最佳解决方案。在这种情况下，搜索速度比深度搜索更快，并且广度优先搜索通常用于寻找最优解。如果节点的“成本”与深度不成正比，那么第一次找到的解不一定是最优解。4.广度优先搜索的效率也取决于目标节点的位置。如果目标节点的深度更深，要搜索的节点数量基本上呈指数增长。接下来，让我们看看如何使用广度优先搜索来解决八位数问题。例如，图2示出了当广度优先搜索应用于八位数难题时生成的搜索树。搜索树中的所有节点都标有相应的状态，每个节点旁边的数字表示节点扩展的顺序。粗线路径表示获得了解决方案。从图中可以看出，这个解决方案是在第26个节点扩展到总共生成46个节点之后获得的。此外，对该图的直接观察表明，不存在具有较短行走序列的解。图4显示了从城市a到城市h的交通图。从图中可以看出，从城市a到城市h，有几个城市要经过。现在我们必须找到穿过这座城市的最少的路线。算法分析看到这个图，很容易想到用邻接矩阵来表示它。0表示行走，1表示不行走。数字。首先想到的是使用队列的想法。阵列A是存储扩展节点的队列。一世。城市记录了过去的城市，和。pre记录趋势前的城市，这样最短的路线可以倒过来。具体过程如下：(1)将甲城纳入队伍，第一队为0，最后一队为1。(2)所有可以直接连接到团队负责人指定城市的城市都将进入团队(如果该城市出现在队列中，则不会进入团队，这可以通过一组来判断)，进入城市的前缀将指向团队负责人的位置。然后向团队领导添加1，以获得新的团队领导城市。重复上述步骤，直到搜索到城市H，搜索结束。Pre可用于反转最小数量的c程序8 _ 1；constru : array1.8，1.8of0.1=(1，0，0，0，1，0，1，1)，(0，1，1，1，0，1，1)，(0，1，1，0，0，1，1，1)，(0，1，0，1，1，0，1)，(1，1，0，1，1，0，0)，(0，0，1，1，1，1，1，0)，(1，1，1，0)，(1，1，1，0，0，1，0)，(1，1，1，1，1，0，0，0)Typenode=record/记录定义city:charpre :整数；结束；varhead，tail，i:integera:array1.100of nod；s:setofA.h；procedure out(d :整数)；/输出过程开始于write(d)。城市)；repeatd:=ad。pre写(-，ad)。城市)；直到去世。pre=0；writeln结束；程序化。begin head :=0；tail :=1；一个。a1。s :=A；重复/第2步(头部)；/在队列的最前面加上一个，然后离开队列到fori:=到8do/搜索城市if(ju顺序(一个的头)。城市)-64，I=0)和(不是(chr (i64) ins)然后/来确定该城市是否已经通过了beginin Inc .(tail)；/在团队末尾添加一个，输入团队a尾部。一条尾巴。是的尾巴。城市；ifa尾巴。城市=尾巴；休息；结束；结束；直到head=tail；结束；BEGIN/主程序doit结束。输出：H-F-A，示例2矩形数组由数字0到9组成，数字1到9代表单元格。单元格定义为相同的上、下、左、右或单元格编号。计算给定矩形数组中的单元格数。例如，阵列有4个单元。算法分析 从文件中读取m*n矩阵数组，将其转换为布尔矩阵并存储在bz数组中；(2)沿着bz阵列矩阵从上到下，从左到右，找到遇到的第一个单元；(3)将细胞位置放在组H中，沿上、下、左、右四个方向将细胞位置放在组中，并将bz数组设为FLASE进入团队后；(4)将H队队长带出队伍，沿上、下、左、右方向进入队伍。进入团队后，bz数组被设置为FLASE；(5)重复4，直到团队H为空，然后找到一个单元格。(6)重复2，直到在基质中没有发现细胞；(7)输出找到的单元格数。ProgrameEx 8 _ 2；常量x :数组1.4of-1.1=(-1，0，1，0)；dy :阵列1.4of-1.1=(0，1，0，-1)；varname，s:stringpic:array阵列1.50，1.79of integer；BZ :阵列1.50，1.79英国；m，n，I，j，num :整数；h :阵列1.4000，1.2集成器；程序it(p，q :整数)；vari，t，w，x，y :整数；begin NIC(num)；bzp，q:=假；t :=1；w :=1；h1，1:=p；h1，2:=q；/遇到的第一个单元格进入团队，沿单元格的四个方向(上、下、左、右)重复方向：=1到4do/搜索单元格开始：=ht，1dxI；y:=ht，2dyI；if(x0)和(x0)和(yw；/结束，直到团队为空；beginfilchar(BZ，sizeof(bz)，true)；num :=0；readln(m，n)；for I :=1 tomdobeginreadln(s)；for j :=1 ondobeginpicI，j:=ord(sj)-ord( 0 )；如果i，j=0，则i，j:=假；结束；结束；i，j然后是doit(i，j)；/在矩阵writeln中查找单元格(NUMBERofcells=，num)；readln如下图所示，在从入口(1)到出口(17)的可行路径图中，数字标签指示检查点。根据记录结构，上述路线图现在存储在下图6中：请设计一个算法，该算法可以找到从存储的数据到出口通过最少数量的检查点的路径。算法分析这个问题是一个路径搜索问题。根据该图，从入口(1)到出口(17)可能有多条路径，其中只有一条最短路径，那么如何找到最短路径呢？根据问题的含义，使用数组“否”来存储每个门号，并使用数组“预”来存储访问门号的前一个门号。事实上，这个主题是一个典型的图遍历问题。我们可以使用图的广度优先遍历，并使用队列来存储顶点之间的连接。从条目(1)开始，首先将其排队，然后将(1)的所有关联顶点排队，即访问一个顶点，将其后续顶点排队，并存储其前置顶点，直到进入出口(17)。最后，从出口门号(17)开始并返回其先前的门号，直到入口门号(1)，返回的搜索路径是最短的路径。从表中可以看出，出口门号(17)的最短通路是：(17)；(16)；(19)；(18)；(1)。因此，我们获得了广度优先遍历的基本方法来寻找最短路径，如下：假设邻接矩阵用于存储路由图(1，j=1表示1和J连接，1，j=0表示1和J不连接)。设置了另一个队列和一个指示要扩展到哪个顶点的指针变量pos。(1)从入口开始，(1)首先入队，并且(1)的所有后续顶点根据邻接矩阵入队，并且这些后续顶点的先前顶点被存储为(1)；将位置再向后移动一次，继续扩展它，将其后续顶点排队，并存储它们之前的顶点，直到它扩展到出口(目的地(17)；进入队伍前注意后续顶点，必须检查顶点是否已经在队列中，如果已经在，不要进入队伍；这一步可以称为图遍历或扩展。(2)从队列中的最后一个检查点号(出口(17)开始，依次返回到其前一个顶点，向后推得到的路径是最短路径。它主要基于每个顶点的前向顶点。实现如下：1:=1；而一号17DOI :=一1；重复写(，无一号，)；写(“”)；I:=一号前】；UNTILI=0；参考程序让学生完成，文件名ex8 _ 3 . pas .例4迷宫问题如下图所示，给出一个N*M迷宫图和一个入口和一个出口。制作一个程序，打印从迷宫入口到出口的路径。这里，带有黑色方块的单元格表示它们不能前进(用-1表示)，而带有白色方块的单元格表示它们可以前进(用0表示)。只上下左右。如果没有输出，输出noway。算法分析只要输出一条路径，这就是一个经典的回溯算法问题。在这个例子中，给出了回溯(深度搜索)程序和扩展搜索程序。参见实施参考程序。深度搜索参考程序程序8 _ 4 _ 1；constmaxn=50varmap:array1.maxn，1.maxnof integer；f :布尔值；n，m，I，j，desx，desy，soux，souy，totstep:integer整数；route:array1.maxnof cordx，y :整数；结束；proceduremove(x，y，step :整数)；x，y:=步；/走一步，标记它，写下步数，路线步。路线步骤】。y:=y/记住路径if (x=destx)和(y=desty ),然后开始f:=truetotstep:=stependelsebeginif(ym)和(映射x，y 1=0)然后移动(x，y 1，步骤1)；/如果不是fand (xn)和(映射x1，y=0，则向右移动(x1，y，步骤1)；/如果不是fand (y1)和(映射x，y-1=0)，则移动(x，y-1，步骤1)；/如果不是fand (x1)和(映射x-1，y=0)，则移动(x-1，y，步骤1)；/向上结束；结束；BEGINreadln(n，m)；fori:=的n行m列迷宫/读入迷宫，0表示on，-1表示no beginforj:=1 tomdoread(地图I，j)；readln结束；写入(inputtheinter :)；readln(soux，souy)；/条目写入(input thee xit :)；readln(desx，desy)；/退出f:=false/f=false表示没有解决方案；F=true表示已找到解决方案移动(soux，souy，1)；if thenfori:=1 to tottstepdo/输出直线迷宫路径write(路线I:4)；elsewriteln(noway .)；根据全国人民代表大会(NPC)的报告，中国全国人民代表大会(NPC)于15日在北京举行会议。constmaxn=50u :阵列1.4ofinteger=(0，1，0，-1)；w :阵列1.4ofinteger=(1，0，-1，0)；varmap:array1.maxn，1.maxnof integer；f :布尔值；n，m，I，j，desx，desy，soux，souy，head，tail，x，y :整数；route:array1.maxnof cordx，y，pre:integer结束；procedure print(d :整数)；1900年前，德贝格尼弗鲁特(德路).pre)；写(，路线d)。x、路线d。y，)；结束；BEGINreadln(n，m)；fori:=的n行m列迷宫/