[PKU 1077]検索のBFS&A*(下)

60090 ワード

{
この節では引き続きPku 1077について議論する
Zju 1217に付随するテスト
Zju 1217データがより強いか、それとも多測比較が問題を反映できるか
}
8デジタル問題のもう一つの優れたアルゴリズムはA*アルゴリズムである.
A*アルゴリズムは貪欲な思想に基づく検索アルゴリズムである
A*アルゴリズムは、より少ないノードにアクセスしながら、より良い解のセットを見つけることができます.
私たちの検索はいつも検索ツリーを巡っています.
例えばBFSは階層遍歴DFSが先順遍歴である
BFS優先選択深度の低いノード拡張DFS優先選択深度の高い拡張
我々がBFSを用いて8デジタル問題を解決したのは,我々が最も少ないステップ数のスキームを要求したからである.
BFS優先選択深さの低いノード拡張は,解の優劣に対する我々の判断にぴったり合っている.
だからこそ見つけた最初の解が最適解
実際に優劣を深さで判断するだけでは十分ではありません
一つの状態の優劣を判別するために啓発関数を構築することができる.
優れたノードを優先的に拡張し、より優れた解のセットをより迅速に得る
これがA*アルゴリズムの基本です
例1 2 3 4 5 6 7 x 8は、8 7 6 5 4 2 xより明らかに優れている
啓発関数の計算を経て,前者の
しかし、これは私たちの主観的な感じにすぎません.
量子化しなければなりません
ヒント関数の役割は、ノードからターゲットノードまでの距離を推定し、ノードの深さを加えることです.
現在の状態の優劣がおおよそわかる
「推定距離」は本当にノード間の距離を算出するものではありません
ターゲットノードに近いか遠いかを他の関数で判断できます
推定するだけだから啓発関数には良し悪しがある
良い啓発関数はすぐに解を見つけて最適解になります
悪い啓発関数は泥沼に陥って抜け出せないだけだ
良い啓発関数を設計することはA*アルゴリズムの鍵である.
 
8デジタル問題のヒント関数には多くの種類があります
目標位置にある数の個数を直感的に啓発関数として用いることができる.
この啓発関数はまだ少し粗末だ.
8 2 3 4 5 6 7 xの「トラップ」を簡単に構築できます
6個の数が帰位したように見えますが、これは多くのステップを歩かなければならない状態です.
より良い啓発関数は,各数とターゲット位置のマンハッタン距離を累積して状態の啓発値を決定することである.
このような啓発関数をテストすることで、初めて解を得たときに最適解になることがよくあります.
この啓発関数は優れていると言える.
 
特定の実装では、検索されたステータスを格納するためにいくつかのデータ構造を使用する必要があります.
*すべての状態を1枚のテーブル{q:array of string[9];prev,dep,ans,b:array of longint}で保存
*Hashテーブル{Hash,tab,nxt:array of longint}とBKDRhash関数で重さを判定
*拡張が必要なノードとノードのヒント値{H,f:array of longint}を優先キューで保存
具体的なアルゴリズムは難しくありません
BFSと似ていますが、深さが最小のノード拡張ではありません.
*最も優先度の高いノード(スタックトップ)拡張子を取り出して削除します.
*次に、拡張された重複しないノードをスタックとテーブルに挿入してhash値を記録します.
*最適解ではないかもしれませんが、解が見つかったら直接再帰的に出力されます.
しかし,啓発関数がうまく設計されている場合,往々にして最適解である.
 
いくつかのテスト結果を示します
Pkuのデータが弱いのでA*や双方向で検索しても16 ms
しかもPku測定時に測定メモリが正しくありません
7593602
masterchivu
1077
Accepted
5420K
16MS
Pascal
2895B
2010-09-08 23:47:24
小さいサイズのA*を貼って結果を出しましょう
それに比べてZjuのテストはとても強くて
(注意はマルチメジャー)
双方向とA*を測ってみました
2294775
2010-09-09 21:23:53
Accepted
1217
FPC
5980
12328
Master_Chivu
2294769
2010-09-09 21:18:00
Accepted
1217
FPC
5160
11544
Master_Chivu
A*はヒープをメンテナンスするときにlog 2 Nの複雑さが必要だから
ここには良いテスト分析がありますhttp://wenku.baidu.com/view/d18a5a0e7cd184254b353598.html
かなりのイメージ
同じ条件下で裸BFSは7 w個のノードを拡張する
双方向BFSは1000+個A*500+個のみ
どちらが優れているか,どちらが劣っているかを見るのに十分だ.
最后に1つのA*のコードを贴って书くのがとても丑くて书いていない过程はすべてmainの中で积み重ねました
 

  
    
1 { $I+,Q+,R+,S+ }
2   const maxq = 200000 ;
3 base = $FFFFF;
4 goal = ' 12345678x ' ;
5 gx: array [ ' 1 ' .. ' 8 ' ] of longint = ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 );
6 wx: array [ 1 .. 9 ] of longint = ( 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 );
7 wy: array [ 1 .. 9 ] of longint = ( 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 );
8 dx: array [ 1 .. 4 ] of longint = ( 1 , 3 , - 1 , - 3 );
9 d: array [ 1 .. 4 ] of char = ( ' r ' , ' d ' , ' l ' , ' u ' );
10   var q: array [ 1 ..maxq] of string[ 9 ];
11 prev,dep,ans,b,tab,nxt,h,f: array [ 1 ..maxq] of longint;
12 hash: array [ 0 ..base] of longint;
13 u,qs,hs,tt,ans0,x,i,j,p,tx,temp:longint;
14 flag:boolean;
15 ch:char;
16   procedure out(x:longint);
17   begin
18   if x = 0 then exit;
19 out(prev[x]);
20   if ans[x] <> 0 then write(d[ans[x]]);
21   end ;
22   procedure work;
23   begin
24 i: = 0 ;
25 q[ 1 ]: = '' ; qs: = 1 ;
26   while not eoln do
27 begin
28 read(ch);
29 if ch = ' ' then continue;
30 q[ 1 ]: = q[ 1 ] + ch;
31 inc(i);
32 if ch = ' x ' then b[ 1 ]: = i;
33 end ;
34 readln;
35 u: = 0 ;
36   for i: = 1 to 9 do
37 for j: = 1 to i - 1 do
38 if (q[ 1 ][i] <> ' x ' ) and (q[ 1 ][j] <> ' x ' ) and (q[ 1 ][j] < q[ 1 ][i])
39 then inc(u);
40   if odd(u)
41 then begin
42 writeln( ' unsolvable ' );
43 exit;
44 end ;
45 f[ 1 ]: = 0 ;
46 h[ 1 ]: = 1 ; hs: = 1 ;
47   for j: = 1 to 9 do
48 if q[ 1 ][j] <> ' x '
49 then f[ 1 ]: = f[ 1 ] + abs(wx[j] - wx[gx[q[ 1 ][j]]])
50 + abs(wy[j] - wy[gx[q[ 1 ][j]]]);
51 ans0: = 0 ;
52   for i: = 1 to 9 do
53 ans0: = (ans0 * 131 + ord(q[ 1 ][i])) and base;
54 fillchar(hash,sizeof(hash), 0 );
55 tab[ 1 ]: = 1 ; hash[ans0]: = 1 ; tt: = 1 ;
56 nxt[ 1 ]: = 0 ;
57 while hs > 0 do
58 begin
59 x: = h[ 1 ];
60 h[ 1 ]: = h[hs]; f[ 1 ]: = f[hs];
61 dec(hs);
62 i: = 1 ;
63 while true do
64 begin
65 if i shl 1 > hs then break;
66 if (i shl 1 + 1 > hs) or (f[i shl 1 ] < f[i shl 1 + 1 ])
67 then if f[i shl 1 ] < f[i]
68 then begin
69 temp: = h[i]; h[i]: = h[i shl 1 ]; h[i shl 1 ]: = temp;
70 temp: = f[i]; f[i]: = f[i shl 1 ]; f[i shl 1 ]: = temp;
71 i: = i shl 1 ;
72 end
73 else break
74 else if f[i shl 1 + 1 ] < f[i]
75 then begin
76 temp: = h[i]; h[i]: = h[i shl 1 + 1 ]; h[i shl 1 + 1 ]: = temp;
77 temp: = f[i]; f[i]: = f[i shl 1 + 1 ]; f[i shl 1 + 1 ]: = temp;
78 i: = i shl 1 + 1 ;
79 end
80 else break;
81 end ;
82 for i: = 1 to 4 do
83 begin
84 tx: = b[x] + dx[i];
85 if (b[x] = 3 ) and (i = 1 ) or (b[x] = 6 ) and (i = 1 )
86 or (b[x] = 4 ) and (i = 3 ) or (b[x] = 7 ) and (i = 3 )
87 or (tx > 9 ) or (tx < 1 )
88 then continue;
89 inc(qs);
90 q[qs]: = q[x];
91 q[qs][b[x]]: = q[x][tx];
92 q[qs][tx]: = ' x ' ;
93 if q[qs] = goal
94 then begin
95 prev[qs]: = x; ans[qs]: = i;
96 out(qs); writeln;
97 exit;
98 end ;
99 ans0: = 0 ;
100 for j: = 1 to 9 do
101 ans0: = (ans0 * 131 + ord(q[qs][j])) and base;
102 flag: = false;
103 p: = hash[ans0];
104 while p <> 0 do
105 begin
106 if q[tab[p]] = q[qs] then begin flag: = true; break; end ;
107 p: = nxt[p];
108 end ;
109 if flag
110 then dec(qs)
111 else begin
112 prev[qs]: = x;
113 dep[qs]: = dep[x] + 1 ;
114 ans[qs]: = i;
115 b[qs]: = tx;
116 inc(tt); tab[tt]: = qs; nxt[tt]: = hash[ans0];
117 hash[ans0]: = tt;
118 inc(hs);
119 h[hs]: = qs; f[hs]: = dep[qs];
120 for j: = 1 to 9 do
121 if q[qs][j] <> ' x '
122 then f[hs]: = f[hs] + abs(wx[j] - wx[gx[q[qs][j]]])
123 + abs(wy[j] - wy[gx[q[qs][j]]]);
124 j: = hs;
125 while j > 1 do
126 if f[j shr 1 ] > f[j]
127 then begin
128 temp: = f[j]; f[j]: = f[j shr 1 ]; f[j shr 1 ]: = temp;
129 temp: = h[j]; h[j]: = h[j shr 1 ]; h[j shr 1 ]: = temp;
130 j: = j shr 1 ;
131 end
132 else break;
133 end ;
134 end ;
135 end ;
136 end ;
137 begin
138 assign(input, ' eight.in ' ); reset(input);
139 assign(output, ' eight.out ' ); rewrite(output);
140 while not eof do work;
141 close(input); close(output);
142 end .
143

 
A*とても強くて私たちは彼を勉強しなければなりません.
 
BOB HANオリジナル転載は出典を明記してください