ALGORITHM NOTE 反復深化 Iterative Deepening
単純な深さ優先探索では初期状態から最終状態までの最短経路を求めることは不可能でした。しかし、深さを制限した深さ優先探索（深さ制限探索）を繰り返すことによって最短経路を求めることができます。つまり深さの制限 d を増加させながら深さ制限探索を繰り返します。このアルゴリズムを反復深化といいます。 反復深化及び深さ制限探索では高速化を図るために探索空間（探索木）の枝を刈ることが重要になります。探索アルゴリズムでは、現在の状態 n から最終状態までの最短経路コスト h を見積もることができれば枝を刈ることができます。つまり、現在の状態の深さ g に「ここからあと最低でも h 回の状態変化は必要だろう」というコストh を加えた値が深さの制限 d を超えた場合、そこで探索を打ち切ることができます。h は見積もりであって正確な値である必要はありません。h の値が大きいほど探索の速度は上がりますが、大きく
ALGORITHM NOTE 深さ優先探索 Depth First Search
深さ優先探索はグラフにおける深さ優先探索と同様に動作し（グラフのノードを状態とみなします）、初期状態から最終状態に至るまで可能な限り状態変化を繰り返します。ただし、 現在の状態からそれ以上状態変化が不可能な場合 状態変化が一度生成した状態を生成してしまう場合 問題の性質からこれ以上探索しても明らかに無駄があると断定できる場合 などは探索（状態変化）を打ち切って前の状態に戻ります。これをバックトラックといいます。また探索を打ち切るので、「枝を刈る」とも表現されます。 深さ優先探索の深さに制限を持たせた方法を深さ制限探索といいます。つまり、探索の深さがある定められた値 d に達したところで探索を打ち切ります。問題の性質から深さを制限することができれば探索を高速化することができます。 それでは、８パズルを単純な深さ優先探索（深さ制限探索）で解いてみましょう。 以下のプログラムは、例えば 2 8
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
