宽搜 -- 清钟沁桐-- 编程爱好者博客

关于tju1258双向宽搜的做法讨论

经过不懈努力,终于吧tju1258ac了

当然,初看好象是一个简单题,bfs+hash了事,不过并不是那么简单....

一个单纯的正向宽搜程序:

const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);
      maxn=362880;
      maxmm=3;
var restate:array[1..maxn]of boolean;
    queue:array[1..maxn,1..2]of longint;
    mat:array[0..maxmm,1..9]of integer;
    tmpline:array[1..9]of integer;
    recode,tmpstate,co,qf,qr,s:longint;

procedure init;
begin
fillchar(restate,sizeof(restate),false);
qf:=0;qr:=0;
end;

procedure turncode(num:integer;var code:longint);
var s,s1:integer;
    sum:longint;
begin
  sum:=1;
  for s:=1 to 9 do mat[0,s]:=mat[num,s]+1;
  for s:=1 to 8 do
  begin
    inc(sum,(mat[0,s]-1)*dbin[9-s]);
    for s1:=s+1 to 9 do if mat[0,s1]>mat[0,s]then dec(mat[0,s1]);
  end;
  code:=sum;
end;

procedure turnmat(num:integer;code:longint);
var add,dnum,s,s1:integer;
    tmp:longint;
begin
  tmp:=code-1;
  for s:=8 downto 0 do
  begin
    if s>0 then
    begin
      tmpline[9-s]:=tmp div dbin[s]+1;
      dnum:=tmpline[9-s];
      tmp:=tmp mod dbin[s];
    end else dnum:=1;
    for s1:=8-s downto 1 do if dnum>=tmpline[s1] then inc(dnum);
    mat[num,9-s]:=dnum-1;
  end;
end;

procedure inqueue(d1,d2:longint);
begin
  inc(qr);
  queue[qr,1]:=d1;
  queue[qr,2]:=d2;
end;

procedure outqueue(var d1,d2:longint);
begin
  inc(qf);
  if qf>qr then
  begin
    d1:=-1;
    exit;
  end;
  d1:=queue[qf,1];
  d2:=queue[qf,2];
end;

begin
while not seekeof do begin
  init;
  readln(mat[1,1],mat[1,2],mat[1,3]);
  readln(mat[1,4],mat[1,5],mat[1,6]);
  readln(mat[1,7],mat[1,8],mat[1,9]);
  turncode(1,recode);
  tmpstate:=recode;
  inqueue(tmpstate,0);
  outqueue(tmpstate,co);
  while tmpstate<>-1 do
  begin
    if tmpstate=1 then break;
    turnmat(1,tmpstate);
    for s:=1 to 2 do
    begin
      change(1,2,s);
      turncode(2,recode);
      if not restate[recode] then
      begin
        restate[recode]:=true;
        inqueue(recode,co+1);
      end;
    end;
    outqueue(tmpstate,co);
  end;
  if tmpstate=-1 then writeln('UNSOLVABLE') else writeln(co);
end;end.

后果显然是TLE

当时还不知道,其最大深度足有32层之多...!!!

于是,我又想到了反向宽搜,这样的好处是一次搜完:

程序如下:

const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);
      maxn=362880;
      maxmm=2;
var restate:array[1..maxn]of boolean;
    numstep:array[1..maxn]of longint;
    queue:array[1..maxn,1..2]of longint;
    mat:array[0..maxmm,1..9]of integer;
    tmpline:array[1..9]of integer;
    recode,tmpstate,co,qf,qr,s:longint;

procedure init;
begin
qf:=0;qr:=0;
end;

procedure turncode(num:integer;var code:longint);
var s,s1:integer;
    sum:longint;
begin
  sum:=1;
  for s:=1 to 8 do
  begin
    inc(sum,(mat[num,s])*dbin[9-s]);
    for s1:=s+1 to 9 do if mat[num,s1]>mat[num,s]then dec(mat[num,s1]);
  end;
  code:=sum;
end;

procedure inqueue(d1,d2:longint);
begin
  inc(qr);
  queue[qr,1]:=d1;
  queue[qr,2]:=d2;
end;

procedure outqueue(var d1,d2:longint);
begin
  inc(qf);
  if qf>qr then
  begin
    d1:=-1;
    exit;
  end;
  d1:=queue[qf,1];
  d2:=queue[qf,2];
end;

procedure change(num1,num2,op:integer);
var tt:integer;
begin
  mat[num2]:=mat[num1];
  if op=1 then
  begin
    tt:=mat[num2,4];mat[num2,4]:=mat[num2,5];
    mat[num2,5]:=mat[num2,6];mat[num2,6]:=tt;
  end else
  begin
    tt:=mat[num2,1];mat[num2,1]:=mat[num2,2];mat[num2,2]:=mat[num2,3];
    mat[num2,3]:=mat[num2,6];mat[num2,6]:=mat[num2,9];
    mat[num2,9]:=mat[num2,8];mat[num2,8]:=mat[num2,7];
    mat[num2,7]:=mat[num2,4];mat[num2,4]:=tt;
  end;
end;

begin
  init;
  tmpstate:=1;
  restate[1]:=true;
  inqueue(tmpstate,0);
  outqueue(tmpstate,co);
  while tmpstate<>-1 do
  begin
    turnmat(1,tmpstate);
    for s:=1 to 2 do
    begin
      change(1,2,s);
      turncode(2,recode);
      if not restate[recode] then
      begin
        restate[recode]:=true;
        numstep[recode]:=co+1;
        inqueue(recode,co+1);
      end;
    end;
    outqueue(tmpstate,co);
  end;
  writeln('done');
  while not seekeof do
  begin
    readln(mat[1,1],mat[1,2],mat[1,3]);
    readln(mat[1,4],mat[1,5],mat[1,6]);
    readln(mat[1,7],mat[1,8],mat[1,9]);
    turncode(1,recode);
    if not restate[recode] then writeln('UNSOLVABLE') else writeln(numstep[recode]);
  end;
end.
用一个数组记录下所有情况,以后就直接用.

TLE得我郁闷.

不过,我发现了一个结论:一就是刚才所说的32层,另一个就是...没有无解情况...很奇怪吧?不过也是自然的:因为你可以试一试任何一个数都能移到其他任意位置.就是这样...

所以...Go away..."UNSOLVABLE"!!!!

很自然就想到了双向宽搜.

为了避免作弊我暂时不给出程序.

但是,我提供一些数据:

设一个反向搜索的maxdepth,则:

time>2000ms(maxdepth<=12)

time=1400ms(maxdepth=13)

time<1s(14<=maxdepth<=31,都能ac)

从理论上说,maxdepth=32/2=16时,时间是最优的,我当时取的16,ac360ms

但是,因为是多组数据,就不一定了,经过测试,当maxdepth=18时,time<260ms

这里费了不少心血,就是把一个3*3的方阵压缩成一个1-9!的一个一一对应的数.

实际上这是一个O(40)的算法.不够好.

谁能给出更快的压缩方法请指点,如一个O(9)的

拜托了....

给程序吧...不然有人不服气

const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);
      maxn=362880;
      maxmm=2;
      maxbdep=16  (18);

var restate:array[1..maxn]of boolean;
    restate2:array[1..maxn]of boolean;
    numstep:array[1..maxn]of longint;
    queue:array[1..maxn,1..2]of longint;
    mat:array[0..maxmm,1..9]of integer;
    tmpline:array[1..9]of integer;
    recode,tmpstate,co,qf,qr,s:longint;

procedure init;
begin
qf:=0;qr:=0;
end;

procedure inqueue(d1,d2:longint);
begin
  inc(qr);
  queue[qr,1]:=d1;
  queue[qr,2]:=d2;
end;

procedure outqueue(var d1,d2:longint);
begin
  inc(qf);
  if qf>qr then
  begin
    d1:=-1;
    exit;
  end;
  d1:=queue[qf,1];
  d2:=queue[qf,2];
end;

procedure changeback(num1,num2,op:integer);
var tt:integer;
begin
  mat[num2]:=mat[num1];
  if op=1 then
  begin
    tt:=mat[num2,4];mat[num2,4]:=mat[num2,5];
    mat[num2,5]:=mat[num2,6];mat[num2,6]:=tt;
  end else
  begin
    tt:=mat[num2,1];mat[num2,1]:=mat[num2,2];mat[num2,2]:=mat[num2,3];
    mat[num2,3]:=mat[num2,6];mat[num2,6]:=mat[num2,9];
    mat[num2,9]:=mat[num2,8];mat[num2,8]:=mat[num2,7];
    mat[num2,7]:=mat[num2,4];mat[num2,4]:=tt;
  end;
end;

procedure change(num1,num2,op:integer);
var tt:integer;
begin
  mat[num2]:=mat[num1];
  if op=1 then
  begin
    tt:=mat[num2,6];mat[num2,6]:=mat[num2,5];
    mat[num2,5]:=mat[num2,4];mat[num2,4]:=tt;
  end else
  begin
    tt:=mat[num2,1];mat[num2,1]:=mat[num2,4];mat[num2,4]:=mat[num2,7];
    mat[num2,7]:=mat[num2,8];mat[num2,8]:=mat[num2,9];
    mat[num2,9]:=mat[num2,6];mat[num2,6]:=mat[num2,3];
    mat[num2,3]:=mat[num2,2];mat[num2,2]:=tt;
  end;
end;
begin
  init;
  tmpstate:=1;
  restate[1]:=true;
  inqueue(tmpstate,0);
  outqueue(tmpstate,co);
  while tmpstate<>-1 do
  begin
    turnmat(1,tmpstate);
    for s:=1 to 2 do
    begin
      changeback(1,2,s);
      turncode(2,recode);
      if not restate[recode] then
      begin
        restate[recode]:=true;
        numstep[recode]:=co+1;
        if co<maxbdep then inqueue(recode,co+1);
      end;
    end;
    outqueue(tmpstate,co);
  end;
  while not seekeof do
  begin
    init;
    fillchar(restate2,sizeof(restate2),false);
    readln(mat[1,1],mat[1,2],mat[1,3]);
    readln(mat[1,4],mat[1,5],mat[1,6]);
    readln(mat[1,7],mat[1,8],mat[1,9]);
    turncode(1,recode);
    tmpstate:=recode;
    inqueue(tmpstate,0);
    outqueue(tmpstate,co);
    while tmpstate<>-1 do
    begin
      turnmat(1,tmpstate);
      if restate[tmpstate] then break;
      for s:=1 to 2 do
      begin
        change(1,2,s);
        turncode(2,recode);
        if not restate2[recode] then
        begin
          restate2[recode]:=true;
          inqueue(recode,co+1);
        end;
      end;
      outqueue(tmpstate,co);
    end;
    writeln(numstep[tmpstate]+co);
  end;
end.

http://bbs.cqyzedu.com/dispbbs.asp?boardid=24&id=4142

博客介绍

正文

宽搜2006-05-04 22:52:00

评论