指定された頂点のセットを参照する「最小」パス

最短パスの問題を区別するために、最短ではなく最小を使用します。問題は次のとおりです。

有向グラフ$ G =(V、E)$、2つの頂点$ s $と$ t $、$ p $頂点$ x_1、x_2、
ldots、x_p $の集合が与えられます。目的は、訪問された頂点の集合のサイズが最小になるように$
x_1、 ldots、x_p $のすべてを訪問する$ s-t $経路を見つけることです。ここで$ p
$は定数であり、パスは単純である必要はないと仮定できます。

最初は、これは「特定の頂点のセットを訪問する最短パス」問題と同じだと思っていましたが、この問題がTSP問題に還元できることはわかっています。
$ p $は定数なので、$ x_1、 ldots、x_p
$のすべての可能な訪問注文を列挙し、各注文の連続した頂点間の最短経路の和集合を計算することができます。

しかし、パスをシンプルにする必要はないので、最短パスが問題で必要な最小パスと等しいかどうかはわかりません。いくつかの頂点が何度も訪れるという意味では長いが、すべての固有の頂点の数が少ないという意味では小さいという経路を見つけることは可能だと思う。しかし今まで私はそのような例は見つけられません。

私にはアルゴリズムはありませんが、私は問題がポリ時代解決可能であると信じています。助言がありますか?

ベストアンサー

$ s $、$ t $、頂点$ x_i $、$ s $〜$ t $を含む散歩に使用できる頂点の最小集合$ S
$を求めたいとします。無向の場合、これは簡略化することができます。$ S $、$ t $、$ x_i $を含む頂点の最小集合$ S
$を求めて、$ S $が接続されるようにします。

これはシュタイナーツリー問題のグラフであり、NP困難です。あなたは指示されたケースを見ていますが、この問題を指示しても簡単にはできないので、NP困難なままです。方向切れしていない場合の減少は、各無向エッジを、各方向に1つずつ2つの有向エッジで置き換えます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です