[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の中で积み重ねました
A*とても強くて私たちは彼を勉強しなければなりません.
BOB HANオリジナル転載は出典を明記してください
この節では引き続き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オリジナル転載は出典を明記してください