巡回セールスマン問題（TSP）と中国人郵便配達問題（CPP）の違いは何ですか？
私にとっては、どちらも目的地に行き、そして戻って行きたいと思っています。
16978 次
7 に答える
21
グラフはエッジと頂点で構成されています。CPPでは、すべてのエッジを訪問する必要があります。TSPでは、すべての頂点を訪問する必要があります。
于 2010-12-14T20:01:09.577 に答える
11
巡回セールスマン問題は、各都市に1回行き、最短ルートをとることです。
中国の郵便配達問題は、各都市から他の都市への道を見つけることです。
たとえば、ポイントA、B、C、Dの場合、巡回セールスマンはABCDAに行くことができますが、中国の郵便配達員はAB 、 AC 、 ADなどのルートが必要になります。
巡回セールスマンルートには、各ポイント間に直接のルートはありません（上記の例では、ACリンクはありません）。
各都市は頂点であり、各都市間リンクはエッジです。だから、私はXodarapの答えを言い換えているだけだと思います。
于 2010-12-14T20:06:02.970 に答える
3
超シンプルに保つ：
巡回セールスマン問題は、元の都市に戻って（したがって、ハミルトン閉路に沿って）各都市を1回だけ訪問し、この基準を満たすすべての可能なルートの中で最短ルートをとることです（そのようなルートが存在する場合）。そのようなサイクルを見つけること、最短距離でおそらくユニークな最適なサイクルを見つけることを強制することは「難しい」です。
中国の郵便配達問題またはルート検査問題は、元の都市に戻りながら、都市間の各道路を少なくとも1回訪問し、この基準を満たすすべての可能なルートの中で最短ルートをとることです（そのようなルートが存在する場合）。各道路を1回だけ取るソリューションは自動的に最適であり、オイラー閉路と呼ばれます。そのようなサイクルを見つけることは「実行可能」です。
于 2014-04-04T16:58:04.647 に答える
2
2つの主な違いは次のとおりです。
巡回セールスマン問題は、ノードに2回以上アクセスすることはできません。生成されるパスは、すべての異なるノード/都市で構成されます。
中国の郵便配達/ルート検査問題では、生成されたパスに重複ノードが存在する可能性があります（ただし、重複エッジは発生しません）。つまり、取得したルートとは異なるルートを取得する限り、ノードに複数回アクセスできます。
于 2011-03-16T10:37:48.950 に答える
1
巡回セールスマン問題：
都市と都市間の距離を考慮して、各都市を1つだけ訪問するような最短距離のツアーを見つけます。これをグラフと各エッジに関連付けられたコストまたは重みとして視覚化し、各頂点またはノードが1回だけ訪問されるように、最も安価または最小の重みのツアー（ハミルトンパス）を見つけます。これは、考えられるすべてのハミルトン経路を見つけて、その中から最良のものを見つけることと考えることができます。可能なすべてのルートを見つけることは最適化問題であり、NP完全では、この問題の多項式時間解が存在しないことを意味します
中国の郵便配達問題：
巡回セールスマン問題とは対照的に、CPPは、各エッジが少なくとも1回訪問されるように、グラフから最小コストまたは最小重量のツアーを見つける必要があります。問題には多項式の解があり、グラフがオイラーである場合、最適な解はグラフを通してオイラーツアーを見つける必要があります。
それ以外の場合は、グラフを変更してオイラーにし、オイラーツアーを定義します。中国の郵便配達問題の特殊な例は、グラフのすべてのエッジを移動する必要はなく、一部（必要なエッジ）のみを移動する必要がある場合です。このバリエーションは、地方の郵便配達問題と呼ばれ、NP完全です。言い換えると、グラフが与えられた場合、必要なすべてのエッジが少なくとも1回カバーされるように、最小コスト/最小重量のツアーを見つけ、不要なエッジを使用している可能性があります。
于 2011-11-13T00:53:13.680 に答える
1
これは、コンピュータサイエンスの大学のコースで提示されるパスの問題の単なる別のバリエーションだと思います。
中国の巡回セールスマン問題（C-TSP）は、典型的な対称TSP問題です。その簡単な説明は次のとおりです。31の中国の首都とそのペアワイズ距離のリストを考えると、タスクは、各都市を1回だけ訪問する最短のツアーを見つけることです。C-TSPは中規模のTSP問題であり、（31-1）があります。/ 2 = 1.326*1032の可能なルート。
于 2010-12-14T19:40:24.403 に答える