探索空間の並べ替え

ウィキペディア小見出し辞書

探索空間の並べ替え

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/08/21 17:51 UTC 版)

「力まかせ探索」の記事における「探索空間の並べ替え」の解説

全ての解ではなく1つの解が得られればよい場合、力まかせ探索の実行時間の期待値は、解候補を生成する順序に左右される。一般原則として、最も可能性が高い候補からチェックすべきである。例えば無作為な数 n の約数を探す場合、n が c で割り切れる確率は 1/c だから、解候補は小さいほう（つまり 2）からチェックしたほうが逆の順序よりも効率的である。 さらに、正しい解が得られる確率は、それまでの失敗した履歴に影響されることが多い。例えば、1000ビットのビット列 P から値が 1 のビットを探す問題を考えてみよう。この場合、候補としてインデックスを 1 から 1000 まで変化させ、その候補 c が P[c] = 1 のとき解と判定される。ここで、P の先頭ビットが 0 または 1 である確率が等しく、その後のビットはその直前のビットと同じである確率が90%だとする。解候補を 1 から 1000 に順次インクリメントしていった場合、解が得られるまでの候補数の平均は約 6 となる。一方、1,11,21,31...991,2,12,22,32 のように解候補を生成すると、解が得られるまでの候補数の平均は 2 より若干大きいだけである。 さらに一般化すれば、探索空間の数え上げは、それまでの候補が解でなかったという事実を考慮して、次の候補が最も妥当と思われるものとなるよう選ぶべきである。したがって、例えば解が何らかの意味で「かたまって」存在するなら、新しい解候補はそれまでの候補からなるべく遠いものとすべきである。逆に解が「散らばっている」なら、それまでの候補に近いものを順次試したほうがよい。