看板ACMCLUB
标 题Re: [请益] Chinese Postman Problem
发信站批踢踢兔 (Sat Feb 18 10:00:00 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《[email protected] (...)》之铭言：
: 我听说在 Chinese Postman Problem 当中，
: 如果 edge 是没有方向性的，则有个 p-time 的演算法可以解决这个问题。
: 有人可以提供一点这个演算法的资料吗? 谢谢 :)
An algorithm is given in Jack Edmonds and Ellis L. Johnson,
Matching, Euler Tours, and the Chinese Postman, Mathematical
Programming, 5:88-124, 1973.
I remember it works like the following.
1. Find all odd-degreed vertices (V').
2. Find the shorest path for each pair of vertices in V'.
3. Find a minimum weight perfect matching for V', with each pair connected
by an edge with cost found in 2.
4. The answer is the sum of edge cost plus those found in 3.
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.28.26