1. 概要

このチュートリアルでは、均一コスト探索アルゴリズムでパスを取得する問題について説明します。

まず、問題を定義し、それを説明する例を示します。

次に、この問題を解決するための2つの異なるアプローチについて説明します。

2. 問題の定義

ノードを含むグラフがあるとします。 さらに、これらのノードを接続するエッジがあります。 これらの各エッジには、このエッジを使用するためのコストを表す重みが関連付けられています。 また、ソースノードと宛先ノードをそれぞれ表す2つの番号とが与えられます。

私たちのタスクは、均一コスト検索アルゴリズムを使用して、ソースノードから宛先までのパスを見つけることです。 理解を深めるために例を見てみましょう。

次のグラフがあり、次のように与えられたとします。

ノードからノードに移動するには、次の4つのパスがあります。

  1. 、に等しいコストで。
  2. 、に等しいコストで。
  3. 、に等しいコストで。
  4. 、に等しいコストで。

均一コスト検索アルゴリズムを適用すると、ソースノードから宛先ノードに移動するための最小コストが得られます。 この例では、コストは;に等しくなります。 t したがって、アルゴリズムがノード間で検出するパスは。です。

3. 素朴なアプローチ

3.1. 本旨

ここでの主なアイデアは、ソースノードから宛先へのパス上にあるすべてのノードを格納することです。 ノードごとに、次の2つの値を格納します。

  • ：これは、ソースノードから現在のノードへのパスのコストを表します
  • ：これは、ソースノードから現在のノードまでのコストが最小のパス上にあるノードのリストを表します

均一コスト探索中に、前のコストよりもコストが小さい子ノードに到達すると、子ノードの値を新しいコストに更新します。 さらに、子ノードをノードに追加した後、値をノードの値と等しくなるように変更します。

最終的に、ノードの値には、最小のコスト値でソースノードから宛先に到達するパスを表すリストが含まれます。 また、のコスト値は、からに移動するための最小コストに等しくなります。

3.2. 実装

実装を見てみましょう：

最初に、と配列を宣言します。 （ノードからそれ自体へのパスの長さは）に等しいソースノードを除いて、すべてのノードの値は無限大です。 さらに、すべてのノードの値は空のリストです。ただし、ソースノードはソースノードを含むリストと同じです（ノードからそれ自体へのパスにはノード自体のみが含まれます）。

また、コスト値に従って昇順でソートされた探索済みノードを格納するために、空の優先キューを宣言します。

次に、優先キューが空でない限り、複数のステップを実行します。 各ステップで、キューの先頭に配置されたノードを取得し、その子を反復処理します。 子ノードごとに、ノードの値にノードとノードを接続するエッジの重みを加えた値よりも大きい値があるかどうかを確認します。

その場合は、それを優先キューに追加し、現在のノードの値にノードを接続するエッジの重みを加えた値に等しくなるようにその値を更新します。 また、ソースからノードを通過する子ノードに向かうパスのコストが低いため、その値をノードの値と等しくなるように更新します。 次に、ノードをその値に追加します。

ディープコピー手法を使用してリストをコピーする必要があることに注意してください。 リスト自体への参照をコピーするだけでなく、その要素を含むリストのコピーを取得したいと思います。

最後に、を返します。これは、ソースから宛先に移動する最小のコストパスを表すノードのリストを格納します。

3.3. 複雑

ここでの時間計算量は、均一コスト検索の複雑さとは少し異なります。 均一コスト探索アルゴリズムの複雑さは、に等しくなります。ここで、はノードの数、はエッジの数です。 ただし、このアプローチでは各ノードのパスを含むリストを格納するため、このアプローチの複雑さは複雑になります。これは、各リストのサイズが最悪の場合と等しくなる可能性があるためです。 また、各リストの時間を更新する必要がある場合があります。

最悪のシナリオでは、スペースの複雑さはです。これは、ソースノードから現在のノードまでのすべてのノードを保存するたびに発生するためです。

4. 最適化されたアプローチ

4.1. 本旨

前のアプローチと同じ概念を適用しますが、ソースノードから現在のノードへのパス上にあるすべてのノードを保存する代わりに、パス内のノードの前にあるノードを保存するだけです。 以前のアプローチでは、各ノードのは、現在のノードを追加した後の親と同様でした。 したがって、完全なリストをノードにコピーする代わりに、ノードのみを保存できます。

均一コスト探索アルゴリズムが終了したら、宛先ノードをパスに追加し、ノードに移動してパスの先頭に追加します。 ソースノードに到達するまで、ノードを追跡し続けます。 その時点で、ノードからノードへのパスがあります。

4.2. 実装

実装を見てみましょう：

最初に、前のアプローチと同じ配列と優先度キューを宣言します。 また、パス内の現在のノードの前に来る必要があるノードを格納する配列を宣言します。

次に、前のアプローチと同じ手順を実行します。 ただし、ノードの値を更新すると、ノードの値がノードと等しくなるように更新されます。

均一コスト検索を終了した後、ソースから宛先へのパスを格納するリストを宣言します。 また、最初は宛先ノードと等しいを宣言します。 次に、はに等しくありませんが、リストの先頭にを追加し、のに移動します。

値に達するまで移動し続ける理由は、ソースだけに親がないためです。 さらに、パスの最後のノードから最初のノードに移動するため、ノードをリストの先頭に追加します。 後方に移動しているため、リストの先頭に新しいノードを追加します。

最後に、を返します。これは、送信元ノードから宛先へのパスを表すノードのリストを格納します。

4.3. 複雑

ここでの時間計算量はです。ここで、はノードの数、はエッジの数です。 これは、リストをもうコピーしないためです。 代わりに、値を設定するだけです。

ノードごとに1つの値を格納するだけなので、スペースの複雑さはです。

5. 結論

この記事では、均一コスト探索アルゴリズムでパスを取得する問題を紹介しました。 この問題を解決するための2つの異なるアプローチの背後にある主なアイデアを説明し、それらの実装に取り組みました。