→ lanniba:謝謝大大的整理<(_ _)> 09/09 14:19
※ 引述《lanniba (爛泥巴)》之銘言：
: 想請問一下
: 不知道是否有相關或類似的演算法能知道
: 一個無向圖裡面，能夠走完每個"邊"的最短路徑(節點重複走過沒關係)
: 希望有大大可以給我提示@@
這是屬於圖論 graph theory 的問題，
這個問題的正式名稱叫做中國郵差問題 Chinese postman problem，
它是七橋問題（每條邊剛好只走一次）的加強版本，
如果想要學會中國郵差問題的演算法，得先學會七橋問題的演算法。
然後也要想辦法了解一下圖論裡的 shortest path 和 matching 這兩個概念。
中國郵差問題的演算法大意是：
奇點(連接奇數條邊的點)最後一定得重複走到某一條邊，
要讓總路線最短，最好的方式是把奇點與奇點雙雙對對連接起來，盡量減少重複。
找到最短的連接方式之後，
最後再套用七橋問題的解法即可。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.134.133