グラフ内の特定のノードへの最短経路
1. 概要
グラフ理論では、最短経路問題の修正版があるかもしれません。 バージョンの1つは、重み付きグラフで特定のノードにアクセスする最短経路を見つけることです。
このチュートリアルでは、問題を説明し、複数の解決策を提供します。 さらに、提供されているソリューション間の比較を提供します。
2. 問題の定義
この問題では、重み付けされた無向グラフが提供されます。
例として次のグラフを見てみましょう。
ソースノードがであり、ゴールノードがであると仮定します。 また、アクセスする必要のあるノードはとです。 このグラフの最短経路を見つける必要があります。
必要なノードにアクセスしない場合の最短経路は、合計コストが11であることがわかります。 ただし、ノードとにアクセスする必要があるため、選択したパスは異なります。 合計コストが17のパスを選択します。
選択したパスは、から始まり、で終わり、訪問およびノードであるすべてのパスの中で最短であることに注意してください。 たとえば、合計コストが19の別のパスがあります。 ただし、コストが高いため、このパスは選択しませんでした。
3. 2DDijkstraソリューション
3.1. 理論的アイデア
ここで紹介する最初の解決策は、ダイクストラのアルゴリズムの変更です。 この場合、ソースからノードまでの距離を保存するだけでは不十分です。 代わりに、必見のノードを検討する必要があります。
あるノードに到達したとします。 すでにアクセスしたノードが重要であることがわかります。 ただし、すべてのノードが重要なわけではありません。 具体的には、必見のノードの中でどのノードにアクセスしたかを気にします。
したがって、ソースからの各ノードの距離を保持する配列を更新する必要があります。 配列ではなく、配列がである必要があります。 最初の次元は、以前と同様に、ノード自体に対応します。 ただし、 2番目の次元は、どのノードがすでにアクセスされているかを示すことができるビットマスクを表します。
上に示したグラフの例に戻ってスクロールしてみましょう。 訪問する必要のあるノードがとであるとします。 ノードはビットマスク内にインデックス0を持ち、ノードはインデックス1を持っていると見なします。
特定のノードに到達したら、ビットマスクの値を検討します。 たとえば、ビットマスクの値が「01」であるとします。 この場合、それは私たちがすでに訪問したが訪問しなかったことを意味します。 同様に、「10」は訪問に対応しますが、ではありません。「11」は、との両方の訪問に対応します。
したがって、各ノードには、ノードからの最短パスが多数あります。 これらの最短パスのそれぞれは、必要なノードの特定のセットにアクセスするときの最短パスです。 ビット演算子を使用して、ビットマスクを簡単に変更できます。
最終的に、最終的な回答は、ノードに対応し、すべてのビットマスクのビットが1に等しい配列のセル内に格納されます。
3.2. アルゴリズム
説明されているアプローチのアルゴリズムを見てください。
ご覧のとおり、この関数は、指定されたノードID、ビットマスク、およびコストで新しいノードを作成します。
まず、で配列を初期化し、ソースノードをキューにプッシュします。 まだノードにアクセスしていないため、ソースノードのビットマスクはゼロです。 また、コストはゼロです。 さらに、ソースノードの距離をゼロに設定します。
次に、複数の手順を実行します。 各ステップで、キューからコストが最も低いノードを取得します。 このノードへのより短いパスが見つかった場合は、単に次のノードに進みます。
それ以外の場合は、ノードのすべてのネイバーを反復処理します。 ネイバーごとに、新しいビットマスクを計算します。 必見のノードではない場合、ビットマスクは同じままです。 それ以外の場合は、ノードに対応するビットを1に設定します。
これは、ビットマスクとの間でビット単位または演算を実行することによって行われます。 ビットマスクは、1に等しいビットを除いて、すべてのビットがゼロに等しくなります。
その後、新しいコストを計算します。 新しいコストが保存されているコストよりも優れている場合は、配列を更新してキューにプッシュします。
最後に、すべてのビットが1に設定されているビットマスクを使用してノードの距離を返します。 ビットマスクのビット数は1です。 1を引くことにより、必要なビットマスクを取得します。
説明されているアプローチの複雑さはです。ここで、は頂点の数、はエッジの数、はアクセスする必要のあるノードの数です。
4. 順列ソリューション
4.1. 理論的アイデア
もう1つのアプローチは、重要なノードを検討することです。 重要なノードとは、ノード、ノード、および必見のノードを意味します。 まず、重要なノードの各ペア間の最短経路を計算する必要があります。
次に、必見のノードのすべての可能な順列を抽出する必要があります。 順列とは、必見のノードのすべての可能な順序を意味します。
第三に、順列ごとに、このオプションのコストをチェックします。 各オプションは、ノードから開始し、ノードに到達するまで、必ずアクセスする必要のあるノードに1つずつアクセスすることを意味します。
ノードの各ペア間で、最短パスを使用する必要があります。 したがって、計算された最短パスを使用して、重要なノードの任意のペア間の最短パスを見つけます。
4.2. 最短経路を計算する
最短経路を計算するには、次の2つのオプションがあります。
- ダイクストラのアルゴリズムを複数回使用する。 毎回、重要なノードの1つから開始してダイクストラのアルゴリズムを実行します。 これは、グラフのエッジの数が多すぎない場合に役立ちます。 つまり、がよりもはるかに小さい場合に役立ちます。
- Floyd-Warshallアルゴリズムの使用。 Floyd-Warshallアルゴリズムは、グラフ内のノードのすべてのペア間の最短経路を計算します。 このアプローチは、ノードの数が少ない場合に役立ちます。 つまり、がかなり小さい場合に役立ちます。
4.3. アルゴリズム
説明したアプローチの実装を見てみましょう。
まず、前のサブセクションで説明した方法の1つを使用して最短経路を計算します。 次に、必見のノードのすべての可能な順列を計算します。
その後、複数のステップを実行します。 順列ごとに、その中のすべてのノードを反復処理して、答えを計算します。 2つの連続するノードごとに、計算された最短パスを使用します。 終了したら、最後のノードからノードまでの最短経路を計算します。
最後に、より良い答えを得ることができたかどうかを確認します。 その場合、計算された回答を保存します。 最終的には、最もよく計算された答えを返すだけです。
説明されているアプローチの複雑さは、最短経路の計算に使用されるアルゴリズムによって異なります。 すべての順列をチェックする複雑さはです。ここで、はアクセスする必要のあるノードの数であり、はの階乗です。 この理由は、さまざまな順列の数があり、そのコストを計算するために各順列を反復処理する必要があるためです。
ダイクストラのアルゴリズムを使用して最短経路を見つけることの複雑さはです。これは、グラフに多くのエッジがない場合に適しています。
Floyd-Warshallアルゴリズムの使用の複雑さはであり、グラフのノード数が少ない場合に役立ちます。
5. 比較
説明したアプローチを簡単に比較してみましょう。
ご覧のとおり、すべてのアルゴリズムが必要な最短経路を計算します。
ただし、主なアイデアは、最も複雑度の低い計算が可能なアルゴリズムを見つけることです。
アプローチを選択する際に考慮すべき要素は、、、およびです。これらはそれぞれ、ノードの数、エッジの数、および必見のノードの数に対応します。
6. 結論
このチュートリアルでは、特定のノードにアクセスする必要がある最短経路問題の修正バージョンを紹介しました。 まず、説明した問題の例を示しました。 次に、問題を解決するための複数のソリューションを提示しました。
最後に、説明したソリューション間の簡単な比較を示し、各アプローチをいつ使用するかを示しました。
