广度优先搜索8数码问题

1、BFS-Breadth广度优先搜索广度优先搜索First Search【例题例题】八数码难题八数码难题(Eight-puzzle) 在3X3的棋盘上，摆有8个棋子，在每个棋子上标有18中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局和目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。初始状态和目标状态如下：2831647512384765初始状态 目标状态 由于题目要找的解是达到目标的最少步骤，因此可以这样来设计解题的方法：初始状态为搜索的出发点，以此为基准把移动一步后的布局全部找到，检查是否有达到目标的布局，如果没有，再从这

2、些移动一步的每个布局出发，找出移动两步后的所有布局，再判断是否有达到目标的。依此类推，一直到某布局为目标状态为止，输出结果。由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。问题分析问题分析：Transitional283164752831647528314765283164752836417528314765231847652831476528316754832641752836417583214765283714652318

3、47652318476528143765283145761238476523418765281437652831457612384765123784652831675428163754.BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。BFS-Breadth First Search1248359671011121314队列：队列是限定在一端进行插入另一端进行删除的特殊线性表。删除的一端称为队首，插入的一端称为队尾。例如：排队买票，后来的人排在队尾（插入）， 队首的人离开（删除）。通常我们需要两个指针来配合完成工作，即由两个变量来指挥进队和出队的操作。

4、队列的特点：1线性 2队头读队尾写 3先进先出*Head tail(1)数据结构: Type node=record map:array1.3,1.3 of byte; x,y:byte; step:integer; end;Var data:array1.30000 of node; head,tail:longint;*28316475x=2 y=2Step=2tailheadRead head:*(2)扩展规则: 规则规定空格周围的棋子可以向空格移动。我们可看作空格向上、下、左、右4个位置移动，设空格位置si,sj，则有4条规则：我们用数组dx和dy来表示移动时行列的增量，dx:arra

5、y1.4 of integer=(-1,0,1,0);dy:array1.4 of integer=(0,1,0,-1);map si+dx1,sj+dy1 mapsi,sjmap si+dx2,sj+dy2 map si+dx3,sj+dy3 map si+dx4,sj+dy4 移动后新空格的位置可表示为：nx:=si+dxr ny:=sj+dyrIf nx,ny没有出界的话，mapsi,sjmapnx,ny;(3)搜索策略: 利用队列里已存储的状态，不断地做进队出队的操作，其间要注意，每产生一个新的状态，都要对比那些已产生的每一个状态，判断是否有重复的状态出现，并且还要判断是否到了目标终点

6、。1.初始化读入数据2.将初始状态放在队列首3.Repeat 从队列里取出一个状态并以这个状态为准： 向4个方向扩展： 新产生的状态是否和以前的状态重复？ 如果没有的话这个新的状态可以进队 再判是否是目标状态：是就可以退出循环 until队列清空为止4.如果能够达到目标状态输出层数，否则”No Answer” BFS基本框架基本框架procedure bfs;begin head := 0; tail := 1; datatail.data := 初始状态初始状态; datatail.depth := 0; flag := false; repeat inc(head); for i:=1 t

7、o 4 do begin new :=以以datahead的状态扩展出第的状态扩展出第i个状态个状态; if new已经出现已经出现 then continue; inc(tail); datatail.data:=new; datatail.depth := datahead.depth+1; if new是目标状态是目标状态 then begin flag := true; break; end; end; until (tail = head) or flag if flag then output else writeln(No Answer);end;迷宫问题找出一个从入口到出口的最

8、短路径，规定每次可以向四个方向移动找出一个从入口到出口的最短路径，规定每次可以向四个方向移动Answer=10Type node=record x,y:integer; depth:integer; end;Var data:array1.300 of node; head,tail:longint;*x=2 y=1depth=0 x=1 y=1depth=1x=2 y=2depth=12111289103711545612571368910读入初始数据读入初始数据:地图和起始，及终点位置地图和起始，及终点位置head := 0; tail := 1; datatail记录初始状态记录初始状态

9、; flag := false;repeat inc(head); for i:=1 to 4 do begin xx,yy 取以取以datahead的位置向四个方向走的位置向四个方向走1步的位置步的位置 if xx,yy这个位置是终点即停止循环；这个位置是终点即停止循环； if xx,yy没有出界没有出界 then begin 地图地图xx,yy做标记；做标记； inc(tail); 新的新的datatail做相应的记载做相应的记载 end; until (tail = head) or flag;end;找出一个从入口到出口的最少转弯，规定每次可以向四个方向移动找出一个从入口到出口的最少转

10、弯，规定每次可以向四个方向移动Answer=3-10122223333333444556666procedure calc;begin open:=0; closed:=1; 地图地图起点起点:=-1; dataclosed记载起始位置；记载起始位置； repeat inc(open); x y 分别取分别取open坐标位置坐标位置 1.向上：向上：while没出界没遇到障碍一直向上所能达到的位置都进队没出界没遇到障碍一直向上所能达到的位置都进队; 2.向右：同理；向右：同理； 3.向下：同理；向下：同理； 4.向左：同理；向左：同理；until (队空或队空或目标位置目标位置被更新值被更新值);end;Your Main Topic Goes HereYour Main Topic Goes Here Your subtopic goes hereTransitional PageYour Main Topic Goes Here Your subtopic goes hereTrans