A*算法思想（启发函数法）

1A*算法思想（启发函数法）

   A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行。

因此，A*算法只要求产生问题的全部状态空间的部分结点，就可以求解问题了，搜索效率较高。
确定估价函数方法通常是：搜索到该结点的深度+ 距离目标最近的程度。

3. 2 A*算法例题与习题

例1: 8数码难题：2 8 3    1 2 3

               1 6 4 -> 8   4（用最少的步数）

               7   5    7 6 5

用A*算法程序如下:

program num8;
type a33=array[1..3,1..3] of 0..8;
     a4=array[1..4] of -1..1;
   node=record
    ch:a33;
    si,sj:1..3;
    f:byte;
    pnt,dep,next:byte;
    end;
const goal:a33=((1,2,3),(8,0,4),(7,6,5));
       start:a33=((2,8,3),(1,6,4),(7,0,5));
       di:a4=(0,-1,0,1);
       dj:a4=(-1,0,1,0);
var data:array[0..100] of node;
  temp:node;
  r,k,ni,nj,head,tail,depth:integer;
function check(k:integer):boolean;
  begin
   ni:=temp.si+di[k];nj:=temp.sj+dj[k];
   if (ni in [1..3]) and (nj in [1..3]) then check:=true elsecheck:=false;
  end;
  function dupe:boolean;
  var i,j,k:integer;
      buf:boolean;
  begin
   buf:=false;i:=0;
   repeat
    inc(i);buf:=true;
    for j:=1 to 3 do
     for k:=1 to 3 do
      if data.ch[j,k]<>data[tail].ch[j,k]then buf:=false;
   until buf or (i>=tail-1);
   dupe:=buf;
  end;
  function goals:boolean;
   var i,j:byte;
   begin
    goals:=true;
    for i:=1 to 3 do
     for j:=1 to 3 do
      if data[tail].ch[i,j]<>goal[i,j] thengoals:=false;
   end;
   procedure print;
    var buf:array[1..100] of integer;
    i,j,k,n:integer;
    begin
     n:=1;
     i:=tail;buf[1]:=i;
     repeat
      inc(n);buf[n]:=data.pnt;
      i:=data.pnt;
     until i=0;
     writeln('steps=',depth+1);
     for i:=1 to 3 do
      begin
       for k:=n-1 downto 1 do
       begin
        for j:=1 to 3 dowrite(data[buf[k]].ch[i,j]);
         if (i=2) and (k<>1) thenwrite('->') else write('  ');
       end;
       writeln;
     end;
     readln;halt
   end;
function calc_f(a:a33):byte;
var i,j,temp:byte;
begin
temp:=0;
for i:=1 to 3 do
  for j:=1 to 3 do
   if (a[i,j]<>goal[i,j]) and (a[i,j]>0) then inc(temp);
calc_f:=temp+depth+1;
end;
procedure sort(num:integer);
var x,y:word;
begin
y:=head;
repeat
  x:=y;y:=data[x].next;
until (y=0) or (data[y].f>data[num].f);
data[x].next:=num;data[num].next:=y;
end;
begin
head:=0;tail:=1; data[0].next:=1;
with data[1] do
  begin
   ch:=start;si:=3;sj:=2;
   pnt:=0;dep:=0;next:=0;
  f:=calc_f(ch);
  end;
repeat
head:=data[head].next;temp:=data[head];
depth:=temp.dep;
for r:=1 to 4 do
  if check(r) then
   begin
   inc(tail);data[tail]:=temp;
   with data[tail] do
    begin
     ch[si,sj]:=ch[ni,nj];
     ch[ni,nj]:=0;si:=ni;sj:=nj;
     pnt:=head;
     dep:=depth+1;
    f:=calc_f(ch);
    end;
   if dupe then dec(tail) else if goals then print else sort(tail);
   end;
until data[head].next=0;
writeln('no solution');readln;
end.

　

练习：
1.移动棋子游戏：在下列所示的10个格子里，前面两格是空格，后面相间的放着4个A和4个B

A

B

A

B

A

B

A

B

若每次可移动任意两个相邻的棋子进入空格，移动时两棋子不得更动其原来次序目标是将4个A连在一起，空格位置不限。试编程，求出一种方案并输出每移动一次后得棋子状态。