广度优先搜索算法

广度优先搜索算法例八数码难题。在3＊3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局[初始状态]和目标布局[目标状态]，找到一种移动的方法，实现从初始布局到目标布局的转变。2831647512384765283164705283164075283164750283104765283064175283014765203184765283140765283164750083264175283604175083214765283714065280143765283145760283106754283163754……………………………………………………………………综合数据库typenode=recordch:array[1..3,1..3]ofbyte;si,sj:byte;{空格的坐标}pnt,dep:word;{父节点和深度}end;Vardata:array[1..2600]ofnode;temp:node;产生式规则:4条，空格向上，下，左，右四个方向移动生成结点的条件：（1）新状态不出界（2）和已生成结点不重复ni:=temp.si+di[k];nj:=temp.sj+dj[k];withtempdobeginch[si,sj]:=ch[ni,nj];ch[ni,nj]:=0;si:=ni;sj:=nj;pnt:=head;dep:=dep+1;end;r1234方向左上右下di0-101dj-1010搜索策略（BFS）框图：初始head=0Tail=0初始化INIT;初始结点入队结点出队out(temp1)temp←temp1change(temp)Forr:=1to4doCheck(temp)andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail练习：有两个无刻度标志的水壶，分别可装5升水和2升水，设另有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在2升壶中量出1升水来。编一程序解决问题。如图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编程序，由计算机找到从C1到C6的一条路径及路程总长度，要求求出经过城市最少的解和路程总长度最少的解。C63448492264C1C2C5C4C3综合数据库typenode=recordcity:integer;{城市编号}flag:setof[1..6];{到根结点的路径}pnt:integer;{父节点}end;Vardata:array[1..1000]ofnode;temp:node;产生式规则:5条，向R（R=2--6）城市移动生成结点的条件：（1）城市R不在已走路径中（not(Rindata[head].flag)）（2）当前城市到R有路（link[x,r]0）Data[temp].city:=R;Data[temp].flag:=Data[temp].flag+[R];Data[temp].pnt:=head;搜索策略（BFS）框图：初始head=0Tail=0初始化INIT;初始结点入队结点出队out(temp)temp1←tempchange(temp)Forr:=2to6do条件1and条件2ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail翻币问题。有N个硬币（N=6），正面朝上排成一排，每次将5个硬币翻过来放在原来位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找了步数最少的翻法，并把翻币过程及次数打印出来（用O表示正面，＊表示反面）综合数据库typenode=recordr:integer;(由父节点翻了几个正面朝上的硬币得到当前状态)num:integer;(当前状态中硬币朝上的个数)pnt:integer;(父节点位置)end;Vardata:array[1..1000]ofnode;temp:node;产生式规则:6条，即翻R个（R=0，1，2，3，4，5）正面朝上的硬币生成结点的条件：（1）当前状态有多于R个正面朝上的硬币M=R（M表示当前结点正面朝上硬币的个数），否则出现负数（2）当前状态有多于5-R个反面朝上的硬币N-M=5-R（N表示硬币总数），例如当全部是正面时，R只能取5，不能取0—4。这时N=M，只有R=5时，不等式才成立。（3）当前状态已存在状态不重复新结点正面朝上硬币个数=（M-R）+(5-R)搜索策略（BFS）框图：初始head=0Tail=0初始化INIT;初始结点入队结点出队out(temp1)temp←temp1change(temp)Forr:=0to5do条件1and条件2andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail