中国人郵便配達問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

中国人郵便配達問題(ちゅうごくじんゆうびんはいたつもんだい :Chinese postman problem)とは、グラフ理論における問題の一つであり、以下のように定義される。

Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。

解法[編集]

グラフ理論において、グラフ中のすべての辺を1度ずつ通るような閉路が存在するグラフをオイラーグラフといい、その閉路をオイラー路という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことで、オイラーグラフが得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるため、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めることになる。

オイラーグラフの特徴として「すべての頂点の次数(頂点に接続する辺の数)は偶数である」ことが挙げられる。一般の(次数が奇数である頂点を持つ)グラフに対しては、以下の方法に基づいてグラフ中の一部の辺を2本に増やせばオイラーグラフになる。[1]

  1. グラフ中に存在する、次数が奇数であるすべての頂点(これは必ず偶数個になる)を集める。
  2. 上記の頂点を適当に二つずつ組み合わせる。
  3. この組のそれぞれについて、最短経路にあたる辺を列挙し、該当したものをそれぞれ1本増やす。

よって中国人郵便配達問題は、この際に加える辺の距離を最小にするような、次数が奇数である頂点を二つずつ組み合わせる方法を求める問題(最小マッチング)に帰着される[1]。この最小マッチングはO(V^3)時間で求められることが知られている(ただし、そのアルゴリズムは難しいものである)[2]。他の処理もO(V^3)時間以内で行えるため、全体の時間計算量もO(V^3)となる[1]。ただし、Vは頂点の数である。

与えられたグラフGがすでにオイラーグラフである場合は、求める閉路の長さはGの辺の距離の総和である(そのオイラー路自体が条件を満たしている)。一方与えられたグラフGがである場合には、すべての辺を2本に増やさなければならず、求める閉路の長さはGの辺の距離の総和の2倍である。

名称について[編集]

この問題を研究していた中国人数学者の管梅谷(Mei Ko Kuan)にちなみ、当時アメリカ国立標準技術研究所(NIST)に所属していたAlan Goldmanが1962年に付けたものである(参照:Chinese Postman Problem)。

出典[編集]

  1. ^ a b c Saul I. Gass; Carl M. Harris; 森村英典(監訳); 刀根薫(監訳); 伊理正夫(監訳) (1999), 経営科学OR用語大事典, 朝倉書店, ISBN 4254121318 
  2. ^ Bernhard Korte; Jens Vygen; 浅野孝夫(訳); 浅野泰仁(訳); 小野孝男(訳); 平田富夫(訳) (2005), 組合せ最適化―理論とアルゴリズム, シュプリンガー・フェアラーク東京, ISBN 9784431711834 

関連項目[編集]