多項式時間旅行セールスマンツリーを使用する[動的プログラミング]

Question

私たちがN都市を持つ場合、それぞれの都市がバイナリツリーの葉だけである場合、多項式時間である動的プログラミング解を考え出すことは可能でしょうか？私はすべての都市間の最小限の距離を見つけようとしていますが、それは最初に深度を旅行できるという制約があります。私のアプローチは、ボトムアップを開始し、最も深い内部ノードの各祖先のために最適な進路を計算することです。したがって、これらの各操作の間に距離関数によって評価される4つの都市が存在します。距離（x、y）=距離（y、x）。各作業に4つの都市がある場合、8つの解決策があります。その他の内部ノードはすべて、下位ノードの合計になります。根は基本的には子どもの総数です。私はここで間違った方向に向かったのだろうか？

Answer 1

私はあなたが木であるグラフのTSPを解決しようとしていると仮定しています。この問題の学術的なバージョンは、おそらく良い検索用語である "有界な線幅"のグラフ上でTSPを解くことにあると思われる。 http://www.cs.princeton.edu/~zdvir/apx11slides/erik-scribe.pdfには、「Frederic Dorn、Fedor V.Fomin、およびDimitrios M. Thilikos。Catalan構造およびHマイナーフリーグラフの動的プログラミング」が含まれています。SODA '08：第19回 年次ACM-SIAMシンポジウムDiscrete Algorithms、631ページ（640。SIAM、2008年）」を、数学者にとってプログラマーよりも興味があると思われる論文に追加する。

あなたが最適なツアーを与えられたとします。内部ノードの2人の子供を見て、このツアーが内部ノードを横切る回数を数えます。それが2回以上交差する場合は、短いカットを取ることでツアーを短縮することができます。これらの交差点のうち2つを壊し、サブツリーからサブツリーに移動するのではなく、各サブツリー内のリンクに変換します。したがって、最適なツアーでは、各内部ノードが交差すると、1つのサブツリー内のすべての都市を訪問するパス、別のサブツリーへの旅行、そのサブツリー内のすべての都市を訪問するパス、ツアーをアップする。

おそらく非効率的だが多項式の動的計画法は、各内部ノードにおいて、その内部ノード内の各都市の対について、都市Aから都市Bへの最良の旅行のコストを計算し、そのノードの下にある都市（または「同じ側にある都市 - これをしない」というマーカー）を選択します。子どもから計算された情報を使って内部ノードごとにこれを実行することができます。最上部では、提供されている最善のパスと残りのリンクのコストを考慮して最短ツアーを実施します。