トラベリングセールスマン：どのようにしてグラフを前処理できますか？

-2

Vの頂点とEの辺を持つ与えられた完全なグラフG（すべての頂点がすべての他の頂点に接続されていることを意味する）でTSPを計算したいとします。トラベリングセールスマン：どのようにしてグラフを前処理できますか？

もう一度質問します。私はうまくいけば今度はそれを得るでしょう。私の目標は単純です：
このグラフGの完全なグラフでは、おそらくグラフに含まれないエッジをどのようにフィルタリングしますか？

2012-01-05 Fatso

TSPがNP完全な問題であるため、前処理によって時間が節約されることはありません。あなたが念頭に置いていた別の目標がありましたか？ – chrisaycock

この「前処理」を実行しようとしているコンテキストとは何ですか？また、これには何が関係していますか？ – NPE

時間は問題ではない、メモリは...私はMSTヒューリスティックを使用しており、ソートされた方法でMSTをトラバースしています。詳細を知りたい場合は、それらを投稿に追加できますが、それは問題のポイントではありません。私は前処理技術に興味があります。 – Fatso

Keld Helsgaun's implementation of Lin-Kernighanは、[eを含む1ツリーの最小コスト] - [1ツリーの最小コスト]（低い方が良い）としてエッジeの品質を測定します。セクション4.1を参照してください。

2012-01-05 19:41:55 fake

ありがとう、偽物。それが正しい方向に私を置きます。 – Fatso

エッジがソリューションツアーで使用されるかどうかを判断する効率的な方法はありません。もし存在すれば、問題の本質的な自己還元性によって多項式時間内に各辺がソリューションツアーの一部であるか否かをチェックし、答えがノーであればエッジを除去することで全体を解くことができます。

2012-01-05 17:19:37

私はツアーに参加できないすべてのエッジを取り除くことについて話しているわけではありません。私はあまりにも遠いものを取り除くことを話しています。それはすでに私のために十分である多くのエッジを削除します。 – Fatso

あなたは、エッジの一部が「遠すぎる」かどうかを知る簡単な方法が必要であると言っています。私は、問題全体を解決するのに必要な同じ作業をせずに、それを知る方法がないと言っています。 –

これは実際には真実ではありません。私は前処理方法を見てきましたが、私はそれらを理解していません。 – Fatso

答えて