[問題] 給定一個無向圖,求將節點兩兩分組的方式

看板Prob_Solve (計算數學 Problem Solving)作者 (皮挺哥)時間3月前 (2024/04/10 15:45), 3月前編輯推噓3(302)
留言5則, 3人參與, 2月前最新討論串1/1
大家早 :D 小弟日前遇到這個問題,想了幾天還沒想到暴力以外的做法 希望版上的大神可以出手相救 -- 給定一個無向有權圖,求將各個節點兩兩分組的方式 節點必須用完且每個節點只能用一次 所有組合方式或 iteration 的方法皆可 節點數量應該 < 50 舉例來說 https://imgur.com/nm8kv4x.png
有三種組合方式: 1. (0, 4) (1, 5) (2, 3),權重總和為 6 2. (0, 1) (2, 3) (4, 5),權重總和為 11 3. (0, 5) (1, 4) (2, 3),權重總合為 15 根據權重總和進行 iteration ,順序會是先 1 -> 2 -> 3 先謝謝大家了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.25.193.156 (瑞士) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1712735151.A.A6B.html

04/10 19:18, 3月前 , 1F
也就是說, 對所有 perfect matching 依權重和列舉出來這樣?
04/10 19:18, 1F
對!原來這東西叫 perfect matching 我用這個關鍵字再搜尋看看 ※ 編輯: petingo (185.25.193.156 瑞士), 04/10/2024 19:38:50 找到解法了 先建一張表紀錄各點可以到達的比自己大的點(key 為起始點,value 為可到達的點) 以上面的例子來說,就是 0 -> 1, 2, 4, 5 1 -> 4, 5 2 -> 3, 4 4 -> 5 然後由小到大 iterate key,並維護一個陣列 combinations 儲存至今為止所能形成的 match 每次 iteration 結束時,刪除 combinations 中不包含當前 key 的 match 由於後續的迭代不會再出現 <= 當前 key 的值,因此該組合不可能為 perfect matching 不知道時間複雜度該怎麼算 但跑起來還算快(? Python code: https://gist.github.com/Petingo/f13bdd820e98a4dead3a36370b78b0b8 ※ 編輯: petingo (185.25.193.156 瑞士), 04/12/2024 00:09:49

04/12 03:49, 3月前 , 2F
不是應該用 Edmonds's matching algorithm 嗎
04/12 03:49, 2F
我對 Edmond's matching algorithm 的理解是他只能找到其中的一組解? 但我需要所有可能的組合 維基百科說計算 perfect matching 的數量是 #P-complete,所以要找所有組合大概也只 能硬爆吧? ※ 編輯: petingo (185.25.193.156 瑞士), 04/12/2024 16:13:21

04/16 21:17, 2月前 , 3F
如果要窮舉的話大概就只能暴力解了..
04/16 21:17, 3F

04/19 09:25, 2月前 , 4F

04/19 09:32, 2月前 , 5F
文章代碼(AID): #1c5aElfh (Prob_Solve)
文章代碼(AID): #1c5aElfh (Prob_Solve)