力まかせ探索
他にも探索手法やメタヒューリスティクスは多数存在し、解に関する様々な知識を利用するよう設計されている。
ヒューリスティクスは、探索の一部を早めに切り捨てるのにも使われる。例として、ゲーム理論におけるミニマックス法がある。これは、探索の初期段階で多くの部分木を排除する。
構文解析などの分野では、チャートパーサなどの技法が問題の制約条件を利用して、指数関数的複雑さの問題を多項式レベルの複雑さの問題に削減している。
問題の探索空間は、問題を単純化することでも削減できる。例えばコンピュータチェスでは、ある手数で木を刈り込み、残りの木を評価関数で近似することで、完全なミニマックス法の探索木よりもさらに限定された探索木を求めることができる。
全ての解ではなく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 より若干大きいだけである。
さらに一般化すれば、探索空間の数え上げは、それまでの候補が解でなかったという事実を考慮して、次の候補が最も妥当と思われるものとなるよう選ぶべきである。したがって、例えば解が何らかの意味で「かたまって」存在するなら、新しい解候補はそれまでの候補からなるべく遠いものとすべきである。逆に解が「散らばっている」なら、それまでの候補に近いものを順次試したほうがよい。