6.3 DSL によるヒューリスティック関数の記述方法
7.1.3 逐次実行における測定結果の考察
まず，表7.2の8パズルの測定結果について述べる．非決定実行は従来のBFSによる 探索で，全状態空間を構築したものである．A*探索では，解の深さが大きいほど展開され る状態数が大きくなっていき，実行時間も増加している．また，解に到達しない初期配置 では全状態空間が構築され非決定実行と状態数が最終状態を除いてほとんど同じとなって いる．非決定実行と比べると，A*探索では，初期値1〜3において解を得るまでに展開さ れる状態数が大きく削減されており，大幅な実行時間の向上が見られる．しかし，非決定 実行とA*探索の初期値4の場合では，実行時間はA*探索の方が非決定実行の2倍以上 かかってしまっている．これは，解が見つからない配置のため展開される状態数が変わら ず，各状態におけるヒューリスティック関数の計算時間の分だけ実行時間が増加したため である．
図7.1のA*探索と非決定実行による8パズルの各種処理の割合を見てみると，A*探索 ではヒューリスティック関数の計算時間が約50%近くを占めている．よって，初期値に よっては展開する状態数が大きく削減され全体としての実行時間は向上するが，その分，
実行時間全体におけるヒューリスティック関数の計算時間の割合が増加する．ヒューリス ティック関数の計算は状態展開の際に展開されたすべての状態に対して行われるため，高 コストな処理となっている．また，複雑なヒューリスティック関数の計算の場合にはさら に増加する場合も考えられる．現在，ヒューリスティック関数の計算部分は，グラフアク セスにおけるファンクタの取得の高速化，計算時に使用するレジスタアクセスなど主要な 関数等のインライン展開やマクロ使用などによるC言語のコードレベルの最適化などが 行われているが，以前として改良の余地がある状況となっている．
次に，表7.3では，8パズルよりも規模を大きくして11パズルの問題についての計測結 果を示している．11パズルにおいても8パズルの実行結果と同様になっていて，初期値 によっては状態数を削減し実行時間を向上することができた．
!"#
$!"#
%!"#
&!"#
'!"#
(!"#
)!"#
*!"#
+!"#
,!"#
$!!"#
非決定実行# -.探索#
/0123####################
324/52#6789028#:/82######
259;#1263<=>?#@6:?######
42:?#32=0/32#############
42:?#8647################
2A79:8#36;2#B2A#CDEEFGH##
=0902#?/7I##B<:#CDEEFGH##
=0902#424#?/47932########
=0902#419=1##############
図7.1 各種処理の割合
表7.2 各種初期値における8パズルの実行結果
非決定実行 A*探索
初期状態 初期値1 初期値2 初期値3 初期値4
4 1 3 7 8 2 6 4 7 8 1 3
5 6 0 6 3 4 8 5 0 0 4 5
2 7 8 5 0 1 3 2 1 2 7 6
状態数(stored) 181441 35 872 9806 181440
状態数(Successors) 483840 50 1459 17372 483840
実行時間[s] 5.99 0.01 0.06 0.53 13.95
mem[MB] 63.83 2.01 2.29 5.28 63.83
解の深さ 11 25 31 解なし
!"#
$!"#
%!"#
&!"#
'!"#
(!"#
)!"#
*!"#
+!"#
,!"#
$!!"#
-./-01%!# -./-01'!# -./-01)!# -./-01*!# -./-01*(# -./-01+!# 23.145#
図7.2 各種初期値におけるA*探索の状態数の割合
表7.3 各種初期値における11パズルの実行結果
非決定実行 A*探索
初期状態 初期値1 初期値2 初期値3 1 9 8 2 3 6 10 7 9 2 0 6 11 10 0 6 4 3 7 10 11 0 5 4 11 5 1 8 3 4 5 9 2 7 1 8
状態数(stored) 239500801 202 9533 5349417
状態数(Successors) 638668801 317 16259 10614210
実行時間 9936.33 0.03 0.65 392.69
mem[MB] 99488.83 2.08 5.87 2191.84
解の深さ 20 40 60
7.2 並列実行
本節ではA*探索を並列化したときの測定結果とその考察を示す．