习题：八数码难题（双向BFS）

八数码难题（wikioi1225）

【题目描述】

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

【输入描述】

输入初试状态，一行九个数字，空格用0表示。

【输出描述】

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)。

【样例输入】

283104765

【样例输出】

分析：

很经典题目，题意不解释了。

看到最小步骤会想到广搜，本题可以看成是空格移动达到目标状态的问题，记录空格位置和棋盘状态，加入队列不断增加节点入队。同时注意判重，将棋盘转换为九位数（如果第一个数字为0则是八位数），用hash表解决。这样就可以过这道题了。

但是为了达到更好的时间效率，可以使用双向广搜。

双向宽搜，顾名思义就是从两边搜，适用于已知起始状态和目标状态，求最短步骤的题目。

我们可以开两类数组，分别表示正方方向搜索的队列，然后初始，目标状态分别入对应队列，进行扩展节点，直到两个方向搜索相遇时即得出最短步骤。

出于优化时间的目的，我们往往先搜队列中节点少的方向，轮流进行。

具体讲就是：两个方向根据队列中节点数交替扩展节点，每扩展一个节点为，在本队列判重后还要在另一个方向的队列中找是否出现，出现说明相遇，输出最短步骤为正方方向扩展到该节点所需最短步骤。

注意双向广搜时，反方向扩展节点时操作与正方向相反，比如向左移动要变为向右移动，但这点对本题没有影响。

解释一下

head,tail表示队头队尾指针，v表示最短步骤，w是棋盘状态，px,py表示空格位置。

0表示正方向，1表示反方向。彼此可用1-x转换。

以下就是自己写的了双向广搜+hash判重的八数码AC程序。

代码

program puzzle;

const

  maxn=;

type

   hh=^node;

     node=record

       data:longint;

       text:longint;

       next:hh;

   end;

var

  dx:array[..]of longint=(,,,-);

  dy:array[..]of longint=(,-,,);

  hash:array[..,..maxn]of hh;

  head,tail:array[..]of longint;

  w:array[..,..,..,..]of longint;

  b:array[..,..]of longint;

  px,py,v:array[..,..]of longint;

  n,i,m,j,x,y,s,h,t,k,r:longint;

  c:char;

function haha(t,x:longint):boolean;

  var i,j,xx:longint;p:hh;

  begin

    xx:=x mod maxn;

    new(p);

    p:=hash[t,xx];

    while p<>nil do

    begin

      if p^.data=x then begin r:=p^.text; exit(true); end;

      p:=p^.next;

    end;

    exit(false);

  end;

procedure put(t,x:longint);

var q:hh;xx:longint;

begin

   xx:=x mod maxn;

   new(q);

   q^.data:=x; q^.text:=tail[t]; q^.next:=hash[t,xx];

   hash[t,xx]:=q;

end;

procedure bfs(x:longint);

var i,j,u,l,ans,xx,yy,g,tmp:longint;

begin

  head[x]:=head[x]+;

  for i:= to  do

  begin   b:=w[x,head[x]];

    xx:=px[x,head[x]]+dx[i]; yy:=py[x,head[x]]+dy[i];

    tmp:=b[xx,yy];

    b[xx,yy]:=b[px[x,head[x]],py[x,head[x]]];

    b[px[x,head[x]],py[x,head[x]]]:=tmp;

    g:=; ans:=;

    for u:= to  do begin

     for l:= to  do

      begin ans:=ans+g*b[u,l]; g:=g div ; end;

      end;

      if (xx>)and(xx<=)and(yy>)and(yy<=)and(haha(x,ans)=false) then

         begin

           tail[x]:=tail[x]+; px[x,tail[x]]:=xx; py[x,tail[x]]:=yy;

           w[x,tail[x]]:=b; v[x,tail[x]]:=v[x,head[x]]+; put(x,ans);

           if haha(-x,ans)=true then

            begin

              writeln(v[x,tail[x]]+v[-x,r]); k:=; break;

            end;//在另一个方向的队列中查找该节点

         end;

        if k= then break;

      end;

      if k= then exit;

end;

begin

  t:=;

  for i:= to  do begin

   for j:= to  do

   begin read(c);if c='' then begin x:=i; y:=j;end;

   w[,,i,j]:=ord(c)-; s:=s+w[,,i,j]*t; t:=t div ;  end;

   end;

  put(,); put(,s); k:=;//存入两个hash数组

  w[,,,]:=; w[,,,]:=; w[,,,]:=;

  w[,,,]:=; w[,,,]:=; w[,,,]:=;

  w[,,,]:=; w[,,,]:=; w[,,,]:=;

  v[,]:=; v[,]:=; px[,]:=; py[,]:=; px[,]:=x; py[,]:=y;

  head[]:=; head[]:=; tail[]:=; tail[]:=;

  repeat

  if (tail[]>head[])and((tail[]-head[]<tail[]-head[])or(tail[]<=head[]))

    then bfs()

    else if tail[]>head[] then bfs();//交替扩展节点

  if k= then break;

  until ((head[]>=tail[])or(tail[]>=))and((head[]>=tail[])or(tail[]>=));

end.

使用双向广搜，时间效率大大提高，两种方法在不加其它优化的时间效率对比

广搜+hash

双向广搜+hash

巴特西

习题：八数码难题（双向BFS）

最新文章

热门文章