Poj1077 Eight — 八数码问题,A*+Heap=0ms

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

八数码问题,超级经典,某些人说此题不做人生不完整……汗|

解题思路:A*、A*+Heap、双向BFS、BFS(写的难看的话有可能TLE)……

这道题最好的方法是A*+Heap,使用曼哈顿距离和作为估价函数,利用阶乘哈希记录某一状态是否访问,0ms闪过……

还有注意本题是个SpecialJudge,我纠结了一晚上跟样例都不一样还以为自己错了……= =|

大概解释一下:

1.曼哈顿距离:也就是某位置上的数字与目标位置差几步,例如6应该在第二行第三列,而现在在第一行第一列,则曼哈顿距离为4。

我们除了空格以外所有的数字的曼哈顿距离和作为估价函数,每次取出小根堆顶元素(曼哈顿距离和最小的)扩展。

2.如何判断某一状态是否到过,防止死循环:利用这样一个哈希函数(注意:该哈希函数是可以保证状态与哈希值一一对应的!!!证明略,去翻数学书吧,很多这样的题都是利用阶乘的某些特殊性质来构造哈希函数,效果极佳,所以只需要一个boolean数组搞定):【不是x的数字的逆序个数(后边解释)】*【(k-1)的阶乘(k指当前的数字是第k个不为x的数,具体见例子)】+【9-x的位置号】*8!。逆序个数指的是该数字前有几个数字比它大。比如数列1 2 3 5 7 4 x 6 8的hash值为:0*0!+0*1!+0*2!+0*3!+0*4!+2*5!+1*6!+0*7!+(9-7)*8!

其中4的逆序个数为2(5和7在他前面),6的逆序个数为1,其它的逆序个数为0。空格的位置为7,因此是(9-7)*8!.这种hash值一定不会超过9!的两倍。

3.队列记录估价、操作字符串、当前数码状态(直接用1~9的integer或者byte数组记录就行)

4.对于unsolveble的数据特殊处理:计算除空格外所有数字的逆序个数总和(前面在第2条里提到逆序个数的概念了),由于目标状态逆序个数为0,所以只要计算出的逆序个数总和为奇数,该数据必然无解。可以扩展为:

如果两个状态的逆序个数和奇偶性相同则这两个状态可达,否则一定不可达。

具体原因,只需要把9个格子看做一行数,左右移动看做向左或向右1个单位,上下移动看做空格与空格往前或后3个单位的那个数交换位置,不难证明这种计算是正确的。(小提示:若空格只向左或向右移动一个格子,只会改变空格和相邻数的位置,不会改变数的逆序值;若向上或向下,则等效为改变了两个数的逆序值,奇偶性仍不变)。

顺便说下,事实证明偶尔拿applepi作为函数名是很涨RP的T_T

Source Code

Problem: 1077 User: lydliyudong
Memory: 1352K Time: 0MS
Language: Pascal Result: Accepted
    • Source Code
type
 arr=array[1..9]of integer;
const
 h:array[1..9]of integer=(1,1,1,2,2,2,3,3,3);
 c:array[1..9]of integer=(1,2,3,1,2,3,1,2,3);
 b:array[0..9]of longint=(1,1,2,6,24,120,720,5040,40320,362880);
var
 q:array[0..7000]of integer;
 f:array[0..7000]of arr;
 d:array[0..7000]of ansistring;
 v:array[0..720000]of boolean;
 a:arr;
 p,i,j,k,start,pp:longint;
 ch:char;

procedure swap(var x,y:integer);
 begin
  x:=x xor y; y:=x xor y; x:=x xor y;
 end;

procedure swaparr(var x,y:arr);
 var z:arr;
 begin
  z:=x; x:=y; y:=z;
 end;

procedure swapstr(var x,y:ansistring);
 var z:ansistring;
 begin
  z:=x; x:=y; y:=z;
 end;

function cal:longint;
 begin
  cal:=0;
  for i:=2 to 9 do
   if a[i]<>0 then
    for j:=1 to i-1 do
     if a[j]>a[i] then inc(cal);
 end;

function hash:longint;
 var
  i,j,k:longint;
 begin
  hash:=0; k:=-1;
  for i:=1 to 9 do
   begin
    if f[p,i]<>0 then inc(k);
    if f[p,i]=0 then inc(hash,(9-i)*b[8])
    else for j:=1 to i-1 do if f[p,j]>f[p,i] then inc(hash,b[k]);
   end;
 end;

procedure insert(t:longint);
 begin
  while t div 2>1 do
   if q[t]<q[t div 2] then
    begin
     swap(q[t],q[t div 2]);
     swaparr(f[t],f[t div 2]);
     swapstr(d[t],d[t div 2]);
     t:=t div 2;
    end
   else break;
 end;

procedure heapify(l,r:longint);
 var
  t:longint;
 begin
  t:=2*l;
  while t<=r do
   begin
    if (t<r)and(q[t]>q[t+1]) then inc(t);
    if q[l]>q[t] then
     begin
      swap(q[l],q[t]);
      swaparr(f[l],f[t]);
      swapstr(d[l],d[t]);
      l:=t; t:=2*l;
     end
    else break;
   end;
 end;

procedure scanf;
 begin
  for i:=1 to 3 do
  for j:=1 to 3 do
   begin
    repeat read(ch); until ch<>' ';
    inc(k);
    if ch='x' then continue;
    a[k]:=ord(ch)-ord('0');
    inc(start,abs(i-h[a[k]]));
    inc(start,abs(j-c[a[k]]));
   end;
 end;

procedure applepi(l,r:longint; ch:char);
 var
  i:longint;
 begin
  inc(p);
  f[p]:=f[1];
  swap(f[p,l],f[p,r]);
  i:=hash;
  if v[i] then begin dec(p); exit; end else v[i]:=true;
  d[p]:=d[1];
  d[p]:=d[p]+ch;
  q[p]:=0;
  for i:=1 to 9 do
   if f[p,i]<>0 then
    inc(q[p],abs(h[i]-h[f[p,i]])+abs(c[i]-c[f[p,i]]));
  insert(p);
 end;

begin
 scanf;
 if odd(cal) then begin writeln('unsolvable'); exit; end;
 p:=1;
 q[p]:=start; f[p]:=a; v[hash]:=true;
 while p>=1 do
  begin
   if q[1]=0 then begin writeln(d[1]); break; end;
   for i:=1 to 9 do if f[1,i]=0 then k:=i;
   if k-3>0 then applepi(k,k-3,'u');
   if k+3<9 then applepi(k,k+3,'d');
   if (k mod 3<>1)and(k>1) then applepi(k,k-1,'l');
   if (k mod 3<>0)and(k<9) then applepi(k,k+1,'r');
   q[1]:=q[p]; f[1]:=f[p]; d[1]:=d[p];
   q[p]:=0; d[p]:='';
   dec(p);
   heapify(1,p);
  end;
end.

One Comment

  1. Pingback: POJ搜索题目列表 – Rainbow & Freda

发表评论

电子邮件地址不会被公开。 必填项已用*标注