セールスマンと中国人の旅行の違いは何ですか？

Question

traveling-salesman problemとchinese postman problemの違いは何ですか？ 私にとっては、どちらも目的地に行き、その後戻ってほしいです。

Answer 1

トラベリングセールスマンは、一度各都市に行き、最短ルートをとっています。

中国の郵便配達員の問題は、各都市から他の都市への道のりを得ることです。

など。ポイントA、B、C、およびD巡回セールスマンがABCDAを行くことができるが、中国の郵便配達はAB たルートを必要に行くとうAC と ADなど

で巡回セールスマンルートはありません。上記の例では、各点の間に直接的にACリンクはありません。

EDIT：
各都市は頂点であり、各都市間のリンクは、エッジです。だから、私は@ Xodarapの答えをやり直していると思う。

Answer 2

• 中国の郵便配達： http://en.wikipedia.org/wiki/Route_inspection_problem
• 巡回セールスマン： http://en.wikipedia.org/wiki/Travelling_salesman_problem

2回の記事（と私は、グラフ理論のコースを取ったことがないので、私はを通じて話をすることができた簡単な読み取りから、私の帽子）、それは "CPP"はすべてのエッジを訪問することが含まれ、 "TSP"はすべてのノードを訪問することが含まれているように見えます。

Answer 3

私はそれがcomp sciの大学のコースで提示されたパスの問題のちょっと変わったと思う。

中国旅行セールスマン問題（C-TSP）は、一般的な対称TSPの問題です。その簡単な の説明は次のとおりです。31の中国の首都とその対の距離のリストを与えられたタスクは、各都市を正確に一度訪れる最短の可能なツアーを見つけることです。 C-TSPは中規模の TSP問題であり、（31-1）！/ 2 = 1.326 * 1032の可能なルートがあります。

Answer 4

グラフはエッジと頂点で構成されています。 CPPでは、すべてのエッジを訪問する必要があります。 TSPではすべての頂点を訪問する必要があります。

Answer 5

2の主な違いは次のとおりです。

巡回セールスマン問題が複数回ノードを訪問することができません。生成されるパスは、すべての異なるノード/都市で構成されます。

中国の郵便配達員/ルート検査の問題では、作成されたパスにノードが重複している可能性があります（エッジは重複しません）。私。ノードは、限り、あなたはにかかったよりも、あなたが外に別のルートを取るよう複数回訪問することができます

Answer 6

を巡回セールスマン問題の旅：。 考えると都市と都市の間の距離を、それが各都市を訪問するように、最短距離ツアーを見つけますちょうど1つ。これをグラフと各エッジに関連するコストまたは重みとして視覚化すると、各頂点またはノードが正確に1回訪問されるように、最も安価または最小のウェイトツアー（ハミルトニアンパス）を見つけることができます。これはハミルトニアンの可能性のあるすべてのパスを見つけ、その中で最良のものを見つけることとして考えることができます。すべての可能なルートを見つけることは最適化問題とNPである - 何の多項式時間ソリューションは、この問題

中国人郵便配達問題のために存在していない完全な手段：巡回セールスマン問題への 反して、CPPはA最小コストまたは最小量のツアーを見つけることが必要です各エッジが少なくとも1回は訪れるように、グラフを通る。問題は多項式解を持ち、最適解はグラフがオイラーの場合はグラフを通ってオイラーツアーを見つける必要があります。そうでなければ、グラフを修正してオイラーにし、オイラーツアーを定義します。中国の郵便配達問題の特殊な例は、グラフのすべての辺を移動する必要はなく、その一部だけ（必要な辺）を移動する必要はありません。このバリエーションは農村郵便人問題と呼ばれ、NP完全です。言い換えれば、グラフが与えられれば、少なくとも必要なエッジがすべて少なくとも1回カバーされるように、最小のコスト/最小重量ツアーを見つけ、必要でないエッジを使用している可能性があります。

Answer 7

超シンプルに保つ：

巡回セールスマン問題旅行は、元の街に戻っながら、約（これHamiltonian cycleに沿って歩いて）正確に一度、各都市に行くとも考えられるすべての中で最も短いルートを取っていますこの基準を満たすルート（そのようなルートが存在する場合）。このようなサイクルを見つけることで、最短距離で可能性のあるユニークな最適サイクルを見つけることは "困難"です。

中国人郵便配達問題またはルート検査問題は、このような経路た場合（元の街に戻っている間に少なくとも一度都市間の各ルートを訪問し、この判断基準を満たすすべての可能な経路間の最短ルートを取っについてです存在する）。各ルートを正確に1回とるソリューションが自動的に最適化され、Eulerian Cycleと呼ばれます。そのようなサイクルを見つけることは "実行可能"である。