トラベリングセールスマンへの変更

Question

現在、トラベリングセールスマン問題の最適化アルゴリズムについて学習中です。実際の問題自体を変更せずに問題を修正できるかどうかは疑問でした。それが曖昧に聞こえる場合は、私は明確にしましょう：

TSPの決定バージョン、私はそれを理解し、次のように尋ねる：

頂点Gとコストcのリストを考えると、そこにありますPのコストがせいぜいcであるようなハミルトニアン経路Pであるか？

この質問の一般性とNP完全性を理解しています。しかし、私が考えるように、より直感的な問題の修正版が見つかりました：

が頂点Gおよび特定のハミルトン経路Pのリストを考えると、そのような別のハミルトン経路P *があり、そのPのコスト* Pより小さい？

パラメータはわずかに異なります。最初のものは総コストのみを与え、2番目のものはそのコストを形成する頂点のシーケンス全体を与える。私が疑問に思っていたことは、最初の質問を一般性を失うことなく2番目の質問に還元できるかどうかです。明らかに、Pのコストを単純に計算することで、2番目のものを最初のものに減らすことができます。しかし、第一から第二への逃げた私の把握を減らす。この分野のあらゆる助けに感謝します。

Answer 1

この削減では、コストの最短パスが厳密にcよりも大きくなります。

この操作は、TSPがc = 0を設定し、返されたパスが目的のcより大きいかどうかを確認することで、TSPをTSPに減らすことができるため、少なくとも元のTSPほど難しくなります。

したがって、削減自体はNP困難です。それにもかかわらず、元のTSP（パスを返す）を繰り返し適用することで、グラフに存在するエッジの長さの差が徐々に増加し、オリジナルの質問よりも1ステップ高い位置から徐々に増加します。