はるか
今日はUCS（均一コスト探索）について話すよ。
ふゅか
いいね！UCSってどういうアルゴリズムなの？
UCSとは？
UCSとは日本語で均一コスト探索と呼ばれる、経路探索のアルゴリズムである。UCSはbest-first search（最良優先探索）の一種と考えることができる。best-first searchとは評価関数f(n)の中から一番いいやつを選択するsearchである。
ふゅか
best-first searchの一種なんだね。評価関数f(n)で一番良いノードを選ぶんでしょ？
はるか
そうだよ。評価関数f(n)は始点からノードnまでの累積コストなんだ。
UCSの評価関数
UCSの評価関数は、現在のノードからの累積コストである。具体的には、評価関数$f(n)$は、始点からノード$ n $までのコストである$g(n)$であり、次のように表される。
$f(n) = g(n)$
ここで、$g(n)$ は始点からノード$n$までの実際にかかった経路コストを表す。
UCSの経路探索の例
SからGまでの経路をUCSで求める。
評価関数が小さい順にノードを木構造で展開する。
このことから、S-C-D-Gが最適な経路であることがわかる。
Bは展開しなくても、S-C-D-Gが最適な経路であることはわかりますが、一応展開すると以下のようになる。
UCSの性質
UCSの計算時間
$C^{*}$を最適コスト、$b$を各ノードからの子ノードの数（分岐数）とする。
目的地までのコストが$C^{*}$で、各ステップでゴールに、$\epsilon$ずつ近づく場合、必要なステップ数は次のように表されます。
$step=\left\lfloor\dfrac{C^{*}}{\epsilon}\right\rfloor + 1$
したがって、探索に必要なノード展開数は以下のようになる。
$O(b^{step})=O(b^{\left\lfloor\frac{C^{*}}{\epsilon}\right\rfloor + 1})$