启发式搜索A

启发式搜索启发信息：选择优先结点的标准。（依靠这些启发信息的帮助，能较快地找到目标。)启发式搜索：利用启发信息（启发函数）进行搜索例八数码难题。在3＊3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局（初始状态）和目标布局（目标状态），找到一种移动的方法，实现从初始布局到目标布局的转变。283164751238476528316470528316407528316475028310476512384765283164705283104765203184765023184765123084765283804765123405678451602783123082673综合数据库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(temp)temp1←tempchange(temp)Forr:=1to4doCheck(temp)andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail启发式搜索的基本思路：预先确定好一个函数，它能反映该结点与目标结点的接近程度，这个函数称为启发函数（Heuristicfunction）。例如：设八数码中“未到目标位置的数字个数”为启发函数H(n)=未到目标位置的数字个数（n是结点编号）如果两个结点的启发函数相等，应该先选深度小的结点F(n)=未到目标位置的数字个数+结点n的深度=h(n)+dep(n)搜索策略（BFS）框图：初始head=0Tail=0初始化INIT;初始结点入队结点出队out(temp)temp1←tempchange(temp)Forr:=1to4doCheck(temp)andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail将队列按f(n)排序中国盒子。给定10个盒子排成一行，其中有两个相邻的盒子是空的，其余盒子中有4个A和4个B，如图所示：移动规则：任意两个相邻字母可移到空盒中去，但这两字母的次序应保持不变。目标：全部A在B的左边，如下图：编一程序，从键盘上输入一个初始状态，即一系列A和B及两个0（表示两个空盒子）。找到一种达到目标状态的步数最少的移动计划，并模拟显示移动过程。ABBAABABAAAABBBB综合数据库typenode=recorddata:string[10];(10个盒子的状态)sp:integer;(第一个空盒的位置)f:integer;(估价函数值)dep,pnt,next:integer;(深度、父节点位置、排序链指针)end;varbox:array[1..1000]ofnode;temp:node;产生式规则:9条，把第R、R+1个（1=R=9）字符移入空格生成结点的条件：第一、两个字符在空格左边（Rsp-1）或第二、两个字符在空格右边（Rsp+1）。把第R、R+1个字符移入空格sp、sp+1位置把第R、R+1处设为空格sp:=R搜索策略（BFS）框图：初始head=0Tail=0初始化INIT;初始结点入队结点出队out(temp)temp1←tempchange(temp)Forr:=1to4doCheck(temp)andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail将队列按f(n)排序