均一コスト探索

均一コスト探索（Uniform-Cost Search）とは

均一コスト探索は、重み付きグラフにおける探索アルゴリズムの一つです。このアルゴリズムは、スタートノードからゴールノードまでの経路を探索する際に、経路のコスト（重み）を考慮し、最もコストの低い経路を見つけることを目的としています。特に、グラフの各辺に異なるコストが設定されている場合に有効です。

アルゴリズムの基本原理

均一コスト探索は、最良優先探索の一種であり、評価関数としてスタートノードからの累積コストを使用します。探索はスタートノードから始まり、まだ訪れていないノードの中で最も累積コストが小さいノードを優先的に探索します。このプロセスは、ゴールノードに到達するまで繰り返されます。

このアルゴリズムでは、以下の要素が重要になります。

優先度付きキュー: 次に探索するノードを、累積コストの昇順で保持します。これにより、最もコストの低いノードが優先的に選択されます。
ノード展開: 現在のノードから接続する、まだ探索していないノードを生成します。
コスト計算: あるノードから次のノードへの移動コストを計算し、累積コストを更新します。
訪問済みノード管理: 探索済みのノードを記録し、重複した探索を防ぎます。

幅優先探索との比較

均一コスト探索は、幅優先探索の一般化とみなすことができます。幅優先探索では、すべての辺のコストが等しいと仮定しているため、均一コスト探索の特別なケースと言えます。均一コスト探索では、辺のコストが異なる場合でも、最小コストの経路を探索できます。

ダイクストラ法との関係

均一コスト探索は、ダイクストラ法と密接な関係があります。ダイクストラ法は、グラフのすべてのノードに対して、スタートノードからの最小コスト経路を求めるアルゴリズムですが、これは均一コスト探索をグラフ全体に適用した結果と考えることができます。さらに、ダイクストラ法は、Aアルゴリズムにおいて、ヒューリスティック関数を定数関数とした場合の特殊なケースとも言えます。

アルゴリズムの手順

以下に、均一コスト探索の擬似コードを示します。


function 均一コスト[探索]
visited = 訪問済みノードを管理する集合
queue = ノード評価値で自動的にソートするノードの優先度付きキュー

startNode の評価値 = 0
startNode を visited と queue に追加
while (queue が空ではない)
node = queue の先頭から取り出す
if (IS_GOAL(node)) then
return node
for each (child in EXPAND(node))
evalValue = node の評価値 + COST(node, child)
if (child が visited に含まれない) then
child の評価値 = evalValue
child を queue に追加
else if (evalValue < child の評価値) then
child の評価値 = evalValue
child を queue から削除して追加し直す
return 探索失敗


ここで、以下の関数が定義されています。

`COST(node1, node2)`: ノード `node1` から `node2` への辺のコストを返します。
`EXPAND(node)`: ノード `node` から展開できる隣接ノードの集合を返します。
`IS_GOAL(node)`: ノード `node` がゴールノードであるかを判定します。

アルゴリズムの保証

均一コスト探索は、辺のコストが非負の値である場合に、必ず最小コストの経路を発見することができます。これにより、正確な解を求める必要がある場合に、信頼性の高いアルゴリズムとして利用することができます。

まとめ

均一コスト探索は、グラフ探索において、スタートノードからゴールノードへの最小コスト経路を効率的に探索するための強力なアルゴリズムです。特に、辺のコストが異なる場合にその真価を発揮し、経路探索、スケジューリング、ゲームAIなど、様々な分野で活用されています。

このアルゴリズムを理解することで、より高度な問題解決が可能になるでしょう。

もう一度検索