探索アルゴリズム
2008.02.19 16:17 探索 II

与えられた問題が解析的に解くことが困難な(不可能な)場合には、試行錯誤を繰り返すことによって解を探さなくてはなりません。しかし多くの場合、探索しなければならない空間は膨大であり、どのような経路が解へと導くかは不明です。従って、無駄な探索を避けたり、より速く解を見つけるための工夫が必要です。それらを体系的に行う方法が探索アルゴリズムであり、問題や状況に応じて様々なアルゴリズムが考えられます。
探索のアルゴリズムは、与えられた初期状態から最終状態への状態変化の列を求めます(このような列の長さをコストと言うことにします)。従って探索アルゴリズムでは「状態」そして「状態変化」という概念が重要になります。
例えば、8パズルを探索アルゴリズムで解くことを考えましょう。8パズルとは上図のような1つの空白を含む3×3のパネルを上下左右にスライドさせることによって、パズルを完成させます。
ここで、全てのパネルと空白の位置情報が「状態」であり、パネルを上下左右に動かすことが「状態変化」に相当します。

多くの探索アルゴリズムでは、一度生成した状態を再度生成しないようにするために、探索の空間は木構造になります。木(またはグラフ)のノードが状態を表し、エッジが状態変化を表します。
探索アルゴリズム
- 深さ優先探索 Depth First Search(DFS)
- 幅優先探索 Breadth First Search(BFS)
- 反復深化 Iterative Deepening
- A*アルゴリズム A* Algorithm
- 双方向幅優先探索 Bidirectional BFS
探索で解く問題の例
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |