PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 路徑演算法相關的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (爛泥巴)時間12年前 (2012/09/07 17:39), 編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 最新討論串1/2 (看更多)
想請問一下 不知道是否有相關或類似的演算法能知道 一個無向圖裡面，能夠走完每個"邊"的最短路徑(節點重複走過沒關係) 希望有大大可以給我提示@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 120.126.16.69
推
09/07 17:41, , 1F
Euler trail 的變形問題?
09/07 17:41, 1F
→
09/07 17:42, , 2F
恩恩@@
09/07 17:42, 2F
推
09/07 17:48, , 3F
Chinese Postman Problem, 我記得當一個圖沒有 Euler-
09/07 17:48, 3F
→
09/07 17:48, , 4F
trial 時會需要用 weighted graph matching...
09/07 17:48, 4F
weighted graph matching@@?是再從邊的權重下手囉?
→
09/07 21:22, , 5F
走過每個邊的"最短路徑"? 這樣是連邊都要重複走了吧?
09/07 21:22, 5F
恩恩，應該有可能無法一次就把每個邊都全部走完，有的邊可能要重複走 ※ 編輯: lanniba 來自: 120.126.16.69 (09/07 21:56)
→
09/07 22:13, , 6F
請查 Chinese Postman problem (或T-join problem...)
09/07 22:13, 6F
→
09/07 22:13, , 7F
沒有Euler-circuit的話一定有很多(偶數個)奇點
09/07 22:13, 7F
→
09/07 22:14, , 8F
變成要多加邊 來造出 Euler-circuit
09/07 22:14, 8F
→
09/07 22:15, , 9F
弄一弄會發現求出那些奇點的 All-pair shortest path 後
09/07 22:15, 9F
→
09/07 22:15, , 10F
用一般圖帶權匹配可以解決
09/07 22:15, 10F
→
09/09 14:18, , 11F
感謝s大的提示
09/09 14:18, 11F
‣ 更多 lanniba 的文章
文章代碼(AID): #1GIS3Pvj (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 lanniba 的文章
文章代碼(AID): #1GIS3Pvj (Prob_Solve)