最短ハミルトニアン パス (SHP) 問題の拡張について考えていましたが、それを解く方法が見つかりませんでした。私はそれがNP完全であることを知っていますが、問題を単純にブルートフォースしたくないので、ここでアイデアを求めたいと思いました。
拡張はかなり単純です: n個の頂点を持つ無向で完全な加重グラフが与えられた場合、端点vとuを持つ最短のハミルトニアン パスを見つけます。
したがって、残りのn -2個の頂点は ( n -2)! 方法。これを少し早く解決する方法を見つけようとしていました。この問題を有益な方法で解決する方法を見つけようとする私の努力は、これまでのところ成果を上げていません。
エンドバーテックスの知識を活用する方法を知っている人はいますか? いくつかの疑似コードと一緒に説明することをお勧めします。これは、解が最適であることがわかったために必要です。
エンドノードの知識はかなり制限されており、サイクルを簡単に回避できるため、整数計画法で解決できると思いますが、問題の構成を実際に活用することはできません。
すべてのノードを接続する最短経路を見つけたい場合は、巡回セールスマンアルゴリズムを調べる必要があります。なぜHSPとしてアプローチするのか正確にはわかりません。私が考えることができる唯一の理由は、開始都市を指定したいということですが、グラフを少し変更することで、それを簡単に修正できるはずです（必要に応じて投稿できます）。
編集：グラフを微調整する方法を追加
1つのノード（Eと呼びます）を追加し、開始ノードと終了ノードにのみ接続します。TSPは、すべてのノードを接続することにより、問題の解決策を計算します。Eは、開始からE、次に終了することによってのみ到達可能であるため、ソリューション（サイクルはい）には、開始-E-終了が含まれます。次に、Eとの間の2つのエッジを削除すると、最適なソリューションが得られます。TSP内では、開始から終了までのパスが最適になります。
メタヒューリスティック アルゴリズムを使用できます。それらには多くの種類があります (ローカル検索、建設的検索など)。それらの 1 つは、以下に基づいている可能性があります。
頂点のセット X に属する各 x について:
- x C に最も近い頂点のセットを見つけます。
-
パス P にそれらの 1 つを含めるために、セット C をフィルター処理します。
パス P.
エンド。