1. 概要

このチュートリアルでは、すべてのノードにアクセスするグラフで最短経路を見つける方法について説明します。

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

2. 問題の定義

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

私たちのタスクは、与えられたグラフのすべてのノードを通過する最短経路を見つけることです。

2つのノード間の最短パスであり、との間のすべての可能なパスの中で最小のコストを持つパスであることを思い出してください。

このタスクでは、すべての可能な開始ノードと終了ノードをカバーするすべてのパスを探します。 また、同じノードに複数回アクセスできます。 理解を深めるために例を見てみましょう。

次のグラフがあるとします。

ご覧のとおり、特定のグラフのすべてのノードを通過するパスは多数ありますが、それらの中で最短パスであり、コストは;に等しくなります。 t したがって、すべてのノードを訪問する特定のグラフの最短経路のコストは、。に等しくなります。

3. ブルートフォースアプローチ

3.1. 本旨

ここでの主なアイデアは、可能なすべてのパスを生成し、最小のコストを持つパスを取得することです。

まず、ノードの可能なすべての順列を生成します。 各順列は、グラフ内のノードにアクセスする順序を表します。 パスのコストは、2つの連続するノードごとのすべての最短パスの合計に等しくなります。

次に、Floyd-Warshallアルゴリズムを使用して、2つの連続するノードごとの最短経路を計算します。 Floyd-Warshallアルゴリズムがグラフ内のノードのすべてのペア間の最短経路を計算することを思い出してください。

最後に、グラフ内のすべてのノードにアクセスする最短パスは、考えられるすべてのパスの中で最小のコストになります。

3.2. 実装

実装を見てみましょう：

最初に、と呼ばれる配列を宣言します。これは、Floyd-Warshallアルゴリズムを使用して、指定されたグラフ内のノードのすべてのペア間の最短経路を格納します。

次に、たどることができるすべての可能なパスを表すすべての可能な順列を生成します。 次に、順列ごとに、2つの連続するノードごとの最短パスの長さを加算してコストを計算します。 現在の順列のコストを計算した後、が値よりも小さいかどうかを確認してから、を更新します。

最後に、を返します。これは、指定されたグラフのすべてのノードを訪問する最短経路のコストを格納します。

3.3. 複雑

ここでの時間計算量はです。 しましょうこの複雑さの背後にある理由を調べてください。

まず、Floyd-Warshallアルゴリズムには複雑さがあります。 次に、ノードのすべての異なる順列の数はの階乗に等しく、各順列について、それを通過することによってそのコストを計算するので、それはです。

したがって、全体の複雑さはになります。

4. Dijkstraアプローチ

4.1. 本旨

このアプローチでは、ダイクストラアルゴリズムの修正バージョンを使用します。 状態ごとに、現在のノードに加えて、訪問したすべてのノードを追跡する必要があります。 したがって、各状態で訪問したすべてのノードを取得するために、それらをビットマスクとして表します。オンになっている各ビットは、以前にこのノードにアクセスしたことを意味します。

最終的に、私たちの答えは、ビットマスクが1でいっぱいの（すべてのノードにアクセスした）すべてのノードの値の中で最小値になります。

4.2. 実装

実装を見てみましょう：

最初に、ノードのサブセットにアクセスするノードへの最短パスを格納する、という配列を宣言します。 また、ノードとビットマスクを格納する優先キューを宣言します。 ビットマスクは、このノードに到達するために訪問したすべてのノードを表します。 この優先キューは、状態のコストに従って、アクセス順に状態を並べ替えます。

次に、各ノードを優先キューに追加し、それらのビットをオンにすることで、各ノードから最短パスを開始しようとします。 次に、ダイクストラアルゴリズムを実行します。

ノードの子ノードを反復処理します。 それぞれについて、現在のノードとノードを接続するエッジの重みよりも大きいノードの特定のサブセットにアクセスする値があるかどうかを確認します。 この場合、ノードの値を更新する必要があります。 また、と現在のビット単位で、または優先度キューに追加します。 このマスクは、ノードのビットをオンにすることを意味します。

最後に、私たちの答えは、すべてのノードを訪問するためのすべてのノードのコストの最小値になります。

4.3. 複雑

ここでの時間計算量はです。ここで、はノードの数であり、はノードのすべての可能なサブセットの数であり、各状態を優先キューに追加します。

5. 結論

この記事では、すべてのノードを訪問する最短経路を見つける問題を紹介しました。 この問題を解決するための2つの異なるアプローチの背後にある主なアイデアを説明し、それらの実装について説明しました。