1

最も広いパスと最長パスの質問の違いは何ですか? より具体的には、なぜ前者は最大スパニング ツリーを見つけることで解決できるのに、後者は解決できないのでしょうか。最大スパニング ツリーを描画すると、必ずしも最長パスが含まれているとは限らないことはすぐにわかりますが、この事実を真にする 2 つの質問の違いが何であるかについて頭を悩ますことはできません。

ありがとう。

4

1 に答える 1

1

これら 2 つの問題の主な違いは、最も広い経路の問題は最適な部分構造を示しますが、最も長い経路の問題は (誰もが知る限り) 最適な部分構造を示さないことです。

具体的には、ノード u からノード v への最も広いパスを考えます。そのパスが中間ノード s を通過する場合、u から v への最も広いパスは、u から s への最も広いパスと、それに続く s からの最も広いパスで構成されている必要があります。そうでない場合は、ソリューションを悪化させることなく、u から s または s から v へのパスの一部をさらに広いパスに置き換えることができます。

ただし、これは最長パスの問題には当てはまりません。u から v への最長パス (暗黙のうちに最長の単純パス) を取り、それがいくつかのノード s を通過する場合、u から s への最長パスの後に s から v への最長パスが続くとは限りません。例：

   2
u --- v
1 \ / 3
   s

u から s への最長パスはパス u - v - s (長さ 5) で構成され、u から v への最長パスは u - s - v (長さ 4) です。

この最適な部分構造のプロパティにより、貪欲なアルゴリズムと (効率的な) 動的計画法を使用して、最も広いパスの問題を効率的に解決できますが、(誰もが知る限り) 最長パスの問題を効率的に解決することはできません。ちなみに、最短経路についても同様の議論を行うことができます (u から v への最短経路が s を通過する場合、u から s への最短経路と s から v への最短経路の連結が得られます)。貪欲なアルゴリズムまたは DP を使用して、最短パスも決定します。

お役に立てれば！

于 2014-08-12T23:40:10.570 に答える