探索アルゴリズム

与えられた問題が解析的に解くことが困難な（不可能な）場合には、試行錯誤を繰り返すことによって解を探さなくてはなりません。しかし多くの場合、探索しなければならない空間は膨大であり、どのような経路が解へと導くかは不明です。従って、無駄な探索を避けたり、より速く解を見つけるための工夫が必要です。それらを体系的に行う方法が探索アルゴリズムであり、問題や状況に応じて様々なアルゴリズムが考えられます。

探索のアルゴリズムは、与えられた初期状態から最終状態への状態変化の列を求めます（このような列の長さをコストと言うことにします）。従って探索アルゴリズムでは「状態」そして「状態変化」という概念が重要になります。

例えば、８パズルを探索アルゴリズムで解くことを考えましょう。８パズルとは上図のような１つの空白を含む３×３のパネルを上下左右にスライドさせることによって、パズルを完成させます。

ここで、全てのパネルと空白の位置情報が「状態」であり、パネルを上下左右に動かすことが「状態変化」に相当します。




多くの探索アルゴリズムでは、一度生成した状態を再度生成しないようにするために、探索の空間は木構造になります。木（またはグラフ）のノードが状態を表し、エッジが状態変化を表します。

探索アルゴリズム

• 深さ優先探索 Depth First Search(DFS)


• 幅優先探索 Breadth First Search(BFS)


• 反復深化 Iterative Deepening


• Ａ*アルゴリズム A* Algorithm


• 双方向幅優先探索 Bidirectional BFS

探索で解く問題の例