中国の郵便配達員問題

グラフ理論と組合せ最適化における、関の経路問題、中国の郵便配達問題、郵便配達ツアー 、または経路検査問題は、（連結された）無向グラフのすべての辺を少なくとも 1 回訪れる最短の閉経路または回路を見つけることです。グラフにオイラー回路（すべての辺を 1 回カバーする閉じた通路）がある場合、その回路は最適解です。それ以外の場合、最適化問題は、結果として得られるマルチグラフがオイラー回路を持つように、複製するグラフ辺の数（または合計の重みが最小となる辺のサブセット）が最小であることを見つけることです。 ^{[1]これは、} NP 困難である巡回セールスマン問題とは異なり、多項式時間で解くことができます。 [ ^{3 ]}巡回セールスマン問題は、巡回セールスマンが訪問したノードを繰り返すことができず、すべての辺を訪問する必要がない点で巡回セールスマン問題と異なります。

この問題はもともと1960年に中国の数学者梅谷関によって研究され、その中国語の論文は1962年に英語に翻訳された。 ^[4]元々の名称「中国郵便配達問題」は彼に敬意を表して名付けられたが、当時アメリカ国立標準技術研究所にいたアラン・J・ゴールドマンかジャック・エドモンズが考案したとする説もある。 ^{[5] [6]}

一般化では、頂点が均等な集合Tを入力として受け取り、奇数次頂点がTの奇数次頂点と正確に一致するグラフ内の最小重みの辺集合を出力として生成する必要があります。この出力はT結合と呼ばれます。この問題、つまりT結合問題も、郵便配達問題を解決するのと同じアプローチで多項式時間で解決できます。

無向経路検査問題は、 T結合の概念に基づくアルゴリズムによって多項式時間で解決できます。T をグラフの頂点の集合とします。エッジ集合J は、J内の奇数個の接続エッジを持つ頂点のコレクションが集合T とまったく同じである場合に、 T結合と呼ばれます。グラフのすべての接続コンポーネントにT内の偶数個の頂点が含まれている場合は常に、T結合が存在します。T結合問題は、可能な限り最小のエッジ数または最小の総重量を持つ T結合を見つけることです。

任意のTについて、最小のT結合（存在する場合）は、Tの頂点をペアで結合するパスから必然的に構成されます。パスは、すべての合計の長さまたは合計の重みが可能な限り小さくなるものになります。最適なソリューションでは、これらのパスの 2 つがエッジを共有することはありませんが、頂点を共有することはできます。最小のT結合は、 Tの頂点上に、指定された入力グラフの最短パスを表すエッジを持つ完全グラフを構築し、この完全グラフで最小重みの完全マッチングを見つけることによって取得できます。このマッチングのエッジは元のグラフのパスを表し、その結合が目的のT結合を形成します。完全グラフの構築と、その中でのマッチングの検索は、どちらも O( n ³ ) の計算ステップで実行できます。 ${\displaystyle {\tfrac {1}{2}}|T|}$

経路検査問題では、T はすべての奇数次頂点の集合として選択する必要があります。問題の仮定により、グラフ全体が連結されており (連結されていない場合は巡回は存在しません)、ハンドシェイク補題により奇数頂点が偶数個あるため、T結合は常に存在します。T結合の辺を 2 倍にすると、グラフはオイラー多重グラフ (すべての頂点の次数が偶数である連結グラフ) になり、これにより、多重グラフの各辺を 1 回ずつ訪れるオイラー巡回が存在することになります。この巡回は、経路検査問題に対する最適解になります。^{[7] [2]}

有向グラフでは、同じ一般的な考え方が適用されますが、異なる手法を使用する必要があります。有向グラフがオイラーグラフである場合、オイラー閉路を見つけるだけで済みます。そうでない場合は、T結合を見つける必要があります。この場合、入次数が出次数より大きい頂点から、入次数が出次数より大きい頂点へのパスを見つけて、すべての頂点の入次数がその出次数と等しくなるようにする必要があります。これは、入次数 1 単位に対して供給 1 単位、出次数 1 単位に対して需要 1 単位がある最小コストフロー問題の例として解決できます。そのため、O(| V | ² | E |) 時間で解決できます。解が存在するのは、指定されたグラフが強く接続されている場合のみです。^{[2] [8]}

平面グラフの最大カットや無向グラフの平均長さの最小回路を見つけることなど、さまざまな組み合わせ問題が中国の郵便配達問題に還元されています。^[9]

中国郵便配達問題にはいくつかのバリエーションがあり、研究されNP完全であることが示されている。^[10]

• 風の強い郵便配達員問題は経路調査問題の変形であり、入力は無向グラフであるが、各辺は一方向と他方向で異なるコストがかかる可能性がある。有向グラフと無向グラフの解法とは対照的に、これはNP完全である。^{[11] [12]}
• 混合中国郵便配達人問題: この問題では、一部の辺は有向であるため、一方向からしかアクセスできない。問題が有向グラフ (または多重有向グラフ) の最小限の走査を要求する場合、それは「ニューヨークの街路清掃人問題」として知られている。^[13]
• k-中国郵便配達問題:指定された場所から始まり、各エッジが少なくとも 1 つのサイクルで横断されるk 個のサイクルを見つけます。目標は、最もコストのかかるサイクルのコストを最小化することです。
• 「田舎の郵便配達員問題」：いくつかの辺を必要としない問題を解く。^[12]

• 巡回セールスマン問題
• アークルーティング
• 混合中国語郵便配達員問題

• ワイスタイン、エリック W.、「中国の郵便配達員の問題」、MathWorld
• ウィキメディア・コモンズのルート検査問題に関連するメディア