Re: [問題] 路徑演算法相關的問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/09/07 23:32)推噓0(0推 0噓 1→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《lanniba (爛泥巴)》之銘言：
: 想請問一下
: 不知道是否有相關或類似的演算法能知道
: 一個無向圖裡面，能夠走完每個"邊"的最短路徑(節點重複走過沒關係)
: 希望有大大可以給我提示@@
這是屬於圖論 graph theory 的問題，
這個問題的正式名稱叫做中國郵差問題 Chinese postman problem，
它是七橋問題（每條邊剛好只走一次）的加強版本，
如果想要學會中國郵差問題的演算法，得先學會七橋問題的演算法。
然後也要想辦法了解一下圖論裡的 shortest path 和 matching 這兩個概念。
中國郵差問題的演算法大意是：
奇點(連接奇數條邊的點)最後一定得重複走到某一條邊，
要讓總路線最短，最好的方式是把奇點與奇點雙雙對對連接起來，盡量減少重複。
找到最短的連接方式之後，
最後再套用七橋問題的解法即可。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.134.133
→
09/09 14:19, , 1F
09/09 14:19, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
