スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




探索アルゴリズム

2008.02.19 16:17  探索 II


8puzzle.gif



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

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

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

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

stateTransition.gif


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

探索アルゴリズム

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

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

  • 反復深化 Iterative Deepening

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

  • 双方向幅優先探索 Bidirectional BFS



探索で解く問題の例
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。