課題のために、 Steiner Treeを作成する必要があります。ただし、使用する必要があるグラフ構造では新しい頂点を挿入できないため、これは典型的な Steiner Tree ではありません。むしろ、テスト ケースは N 個の頂点と M 個のエッジのグラフ構造を定義し、特に X 個の頂点をターゲット ノードとしてマークします。これらは、グラフ内のマークされていない頂点の一部、またはすべてを使用するか、まったく使用しない場合にまたがる必要があるノードです。
この問題に対する私の解決策は
- ダイクストラのアルゴリズムを実装して、すべてのターゲット頂点間の最短経路を見つけます
- 最短経路のそれぞれについて 1:n
- 現在選択されているすべてのパス頂点をセットに抽出します
- 残りのすべての頂点をセットに抽出します
- 現在選択されているパスのすべての頂点 1:m
- ダイクストラを実行して、現在の頂点と他のパスの頂点の間の最短パスを見つけます
- これによりスパニング ツリーが作成される場合は、長さの値でソートされたパスと長さをプライオリティ キューに保存します。
- プライオリティ キューの先頭にポップし、パスを返す
私の問題は、これがダイクストラの最初のアプリケーションを使用して、最小スパニング ツリーより短いパスの可能な始点と終点の頂点のセットを削減する徹底的な検索であることです。
この問題を解決できるヒューリスティックまたはその他のアルゴリズムはありますか?