※ 引述《DJWS.bbs@ptt.cc (...)》之銘言：
: 我聽說在 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