Poj3460 Booksort — IDA*/双向BFS

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

题目大意：给你n(1<=n<=15)本书，编号1~n，初始状态是随便排列的，每次可以抽取其中连续的一段再把这里段插入到其它某个位置，这样称作一次操作，目标状态为书按1~n顺序排列，问最少需要多少次操作，若操作数>=5输出5 or more。

题目看起来并不难，解答树的深度很浅，仅为4，但是每个节点下巨大的分支使得状态异常地巨大：

可以计算出n=15时一个节点的分支大约要到680条之多，680^4大约为maxlongint的100倍！

所以普通的DFS、BFS即使加入Hash判重也是会爆时间或者空间的！再就会想到A*，虽然可以在15s内出解，但是代码复杂度和时间复杂度还是很高，这样的前提还得是要有一个好的估价函数。这时我们很容易想到两种更好的思路，

1.虽然680^4为maxlongint的100倍左右，而680^2并不大，仅有几十万，完全可以分成两半，限制扩展次数为2，双向BFS，或者直接先BFS出一边然后BFS另一边时二分查找。

2.本题的王牌思路：IDA*。这种思路的最经典之处是一个精妙的估价函数。经过试验，单纯的IDDFS是会超时的，我们应该设计一个估价函数，当当前操作次数+估计值>迭代限制时剪掉该枝。当然需要改估计值小于等于实际操作值。这时我们想到了放缩思想。若用这n个节点中，各个节点的后边一个节点的错误总个数，作为估价函数的基本形式，经过仔细观察可以发现，每次操作至多更改三个节点的后面一个节点值。不妨认为最好情况下每次操作都可以将这三个改对，则接下来的最少操作步数为各节点的错误后继节点总个数除以3向上取整。即(tot-1)div 3+1。时间被优化到300MS以内，空间在1000K以内。且代码很短。

Source Code

Problem: 3460		User: lydliyudong
Memory: 852K		Time: 282MS
Language: Pascal		Result: Accepted

• Source Code

type
 arr=array[0..15]of integer;
var
 a,b:arr;
 t,n,i,ID,ans:integer;
 find:boolean;

function check:boolean;
 var
  i:integer;
 begin
  for i:=1 to n do if b[i]<>i then exit(false);
  exit(true);
 end;

function cal:integer;
 var
  i:integer;
 begin
  cal:=0;
  for i:=1 to n-1 do
   if b[i+1]<>b[i]+1 then inc(cal);
  cal:=(cal-1)div 3+1;
 end;

procedure IDdfs(step:integer);
 var
  i,j,k,l,s,f:integer;
  c:arr;
 begin
  if check then
   begin
    ans:=step;
    find:=true;
    exit;
   end;
  f:=cal;
  if step+f>ID then exit;
  for i:=1 to n-1 do//起始位置
   for j:=1 to n-i do//长度
    for k:=i+j to n do//目标位置
     begin
      c:=b;
      s:=i;
      for l:=k-j+1 to k do begin b[l]:=c[s]; inc(s); end;
      for l:=1 to k-i+1-j do begin b[i+l-1]:=c[i-1+j+l]; end;
      IDdfs(step+1);
      if find then exit;
      b:=c;
     end;
 end;

begin
 readln(t);
 repeat
  dec(t);
  readln(n);
  for i:=1 to n do read(a[i]);
  find:=false;
  for ID:=1 to 4 do
   begin
    b:=a;
    IDdfs(0);
    if find then break;
   end;
  if find then writeln(ans) else writeln('5 or more');
 until t=0;
end.