後戻り防止と双方向探索

後戻り防止の効果

1ステップ毎の後者を1つ排除できる。ステップ数が多くなるほど効果が大きくなる。後者が少ないときに特に効果的。

例：

後者数	状態空間	倍率
2^8	256	−
3^8	6561	25.6
4^8	65536	10.0
5^8	390625	6.0

双方向探索の効果

ステップ数を最大で半減できる。これもステップ数が多いほど効果が大きくなるが、メモリを多く消費するようになるのが欠点。メモリ消費の倍率の1/2ほど探索する状態空間を削減できる。双方向探索のうち片方はメモリに蓄える必要があるので、そちらに幅優先探索を用いることで、後戻り防止だけでなく、重複する状態に到達する手を全て刈り取ることができる。

両方組み合わせると、大雑把な試算で次のような改善が期待できる。

例：24パズルの解の存在判定
平均後者数：3.2
最大手：8

反復深化のみ
3.2^8 = 10995.12

双方向探索（反復深化＋後戻り防止）×（幅優先探索＋重複防止）
2.2^4 = 23.4256
23.4*2 = 46.8

改善率：235倍

参考：転倒数の計上のステップ数：24*23/2 = 276

効果はかなり大きい。もっとも、解の判定だけなら転倒数を数えた方がよほど楽だ^^;　そんな結論だと残念なので8パズルを解く場合を考える。M.hiroi(パズルに挑戦！)によれば、変形版ではあるが30手が最大なので、その手数で試算すると、

8パズルの解
平均後者数：2.56

反復深化のみ
2.56^30 = 1.766846e12

双方向探索（反復深化＋後戻り防止）×（幅優先探索＋重複防止）
1.56^15 = 788.6215
800*2 = 1600

改善率：1.125e9倍

となり、反復深化のみでは解くことがまず不可能なレベルの問題が、現実的なコストで解けるようになることがわかる。今回は面倒なので実装はしない（’’

さらなる改良

15パズルになると、これでも大変なので、下限値枝刈り法を用いると良いと思われる。それ以上の問題では、さらに後者関数の数と手順数が増えるので、このような基本戦略が総当たりでの探索は難しい。最短経路探索はあきらめ、問題を分割して考えないと手に負えないだろう。