問題の名前とその解決策のアルゴリズムを探しています。
すべてのノードが他のすべてのノードに接続されている接続ノード（A..Z）のグラフがあります。ノードの特定のサブセット（A、D、K、W）にアクセスするこれらのノードを通る最短経路をプロットしたいと思います。パスには、サブセットに含まれていないノードが含まれる場合があります。つまり、A-> C-> W->D->Kが許容されます。ノード間を移動するコストは負ではありませんが、必ずしも線形である必要はありません。したがって、A->B->CからのパスセグメントはA->Cよりも「短い」可能性があります
巡回セールスマンのバリエーションだと思います。
この問題に特別な名前があるかどうかはわかりませんが、選択したノードの元の巡回セールスマン問題に簡単に還元できます。
すべてのノードのセットをVと選択したノードとしますW。マルチグラフを取得するために、にないノードを折りたたむことから始めWます（グラフのようですが、ノードの同じペアの間に複数のエッジを持つことができます）。ここでの各エッジは、からの単純なエッジまたは一連のエッジとノードの場合がありますV\W。正則グラフに縮小するには、ノードの各ペアで使用可能な最も短いエッジを選択するだけで済みます。他のエッジは明らかに答えの一部ではないためです。次に、縮小グラフの結果として生じる巡回セールスマン問題を解決してから、元のグラフの対応するパスを再構築する必要があります。縮小グラフの各エッジが対応する元のグラフの実際のパスを書き留めました。