II単純な深さ優先探索では初期状態から最終状態までの最短経路を求めることは不可能でした。深さを制限した深さ優先探索(深さ制限探索)を繰り返すことによって最短経路を求めることができます。増加させながら深さ制限探索を繰り返します。このアルゴリズムを反復深化といいます。反復深化及び深さ制限探索では高速化を図るために探索空間(探索木)の枝を刈ることが重要になります。見積もることができれば枝を刈ることができます。超えた場合、そこで探索を打ち切ることができます。見積もりであって正確な値である必要はありません。値が大きいほど探索の速度は上がりますが、大きく見積もりすぎると解を見逃してしまいます。以後必ず必要となる明確なコストを表し下限値と呼ばれます。8パズルにおける下限値を考えてみましょう。各パネルにおける最終状態までのマンハッタン距離の総和マンハッタン距離とは「斜めに進むことができない上下左右だけの移動の総距離による2点間の距離」をいいます。値が大きいので、優位であると言えます。これらの下限値は、深さ優先探索や深さ制限探索にも適用できます。}プログラムには明らかに無駄があります。高速化を図るのであれば、毎回下限値を計算するのではなく、状態変化した際にマンハッタン距離の差分を計算するとよいでしょう。II幅優先探索はグラフにおける幅優先探索と同様に動作し(グラフのノードを状態とみなします)、幅広く状態変化を行います。現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。それでは、8パズルを幅優先探索で解いてみましょう。方向へパネルを移動するような、パズルを解くための経路を出力します。基本的なデータ構造や状態変化の方法などは、深さ優先探索のプログラムと同様です。幅優先探索では生成された状態を記録するためのバッファが必要です。これをmapを使って実現するためには、パズルをクラスとして定義し、異なるパズルを比較するための演算子を定義します。パズルを対応した数字に変換するハッシュ関数を用いれば演算子は必要なくさらに効率化できるでしょう。幅優先探索では探索を展開するために生成された状態が新しいものであればそれをキューに追加します。II深さ優先探索はグラフにおける深さ優先探索と同様に動作し(グラフのノードを状態とみなします)、初期状態から最終状態に至るまで可能な限り状態変化を繰り返します。問題の性質からこれ以上探索しても明らかに無駄があると断定できる場合などは探索(状態変化)を打ち切って前の状態に戻ります。これをバックトラックといいます。探索を打ち切るので、「枝を刈る」とも表現されます。深さ優先探索の深さに制限を持たせた方法を深さ制限探索といいます。達したところで探索を打ち切ります。問題の性質から深さを制限することができれば探索を高速化することができます。それでは、8パズルを単純な深さ優先探索(深さ制限探索)で解いてみましょう。方向へパネルを移動するような、パズルを解くための経路を出力します。このプログラムでは、8パズルを9つの要素を含むchar型の配列で表現しています。生成した状態を保存していないので、一度生成した状態へ状態変化する場合がありますが、深さを30と制限し、状態変化のとき1つ前の状態へ戻らないようにする(プログラム033行目)ことで、探索の空間を狭めています。II与えられた問題が解析的に解くことが困難な(不可能な)場合には、試行錯誤を繰り返すことによって解を探さなくてはなりません。多くの場合、探索しなければならない空間は膨大であり、どのような経路が解へと導くかは不明です。従って、無駄な探索を避けたり、より速く解を見つけるための工夫が必要です。それらを体系的に行う方法が探索アルゴリズムであり、問題や状況に応じて様々なアルゴリズムが考えられます。探索のアルゴリズムは、与えられた初期状態から最終状態への状態変化の列を求めます(このような列の長さをコストと言うことにします)。従って探索アルゴリズムでは「状態」そして「状態変化」という概念が重要になります。8パズルを探索アルゴリズムで解くことを考えましょう。8パズルとは上図のような1つの空白を含む3×3のパネルを上下左右にスライドさせることによって、パズルを完成させます。ここで、全てのパネルと空白の位置情報が「状態」であり、パネルを上下左右に動かすことが「状態変化」に相当します。多くの探索アルゴリズムでは、一度生成した状態を再度生成しないようにするために、探索の空間は木構造になります。木(またはグラフ)のノードが状態を表し、エッジが状態変化を表します。つのクイーンを配置する問題です。つのクイーンを全ての組み合わせについて配置し、上記のコンディションを満たすかをチェックする方法です。通り無論、この天文学的な数の組み合わせを全て調べることは現実的ではありません。通りと大幅に組み合わせ数を少なくすることができます。通りと導くことは容易です。クイーン問題を解くことができます。行目に戻る)、探索を続行します。他のクイーンによって襲撃されているか否かを記録するために、以下の配列を用意します。襲撃されていることになります。とき、クイーンを配置することができます。i-j+N-1)の関係は下図を参照して下さい。IIとてつもない数の"見込みのある解"の中から、解を探さなければならないというような問題は数多く存在します。これらの問題を解くアルゴリズムは、ある起点から出発し、特定の経路を探索することによって、解を見つけます。多くの問題では、どのような経路が解へと導くかが不明です。このような問題を解くためには、可能な経路をすべて探索(総当り)する方法が考えられますが、探索しなければならない空間が膨大な場合には、無駄な探索を避けるためのテクニックが必須となります。見込みのあるすべての探索空間を体系的(計画的)に探索する方法です。バックトラッキングでは、今いる地点からこれ以上探索が不可能と分かった時、または問題の定義によってこれ以上探索しても無駄であると断定できる時に、そこで探索を打ち切り、前の地点に戻って探索を続行します。バックトラックアルゴリズムの良い例となります。masimarock。