作者petingo (皮挺哥)
看板Prob_Solve
標題[問題] 給定一個無向圖，求將節點兩兩分組的方式
時間Wed Apr 10 15:45:47 2024
大家早 :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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1712735151.A.A6B.html
1F：推 LPH66: 也就是說, 對所有 perfect matching 依權重和列舉出來這樣? 04/10 19:18
對！原來這東西叫 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
2F：→ FRAXIS: 不是應該用 Edmonds's matching algorithm 嗎 04/12 03:49
我對 Edmond's matching algorithm 的理解是他只能找到其中的一組解？
但我需要所有可能的組合
維基百科說計算 perfect matching 的數量是
#P-complete，所以要找所有組合大概也只
能硬爆吧？
※ 編輯: petingo (185.25.193.156 瑞士), 04/12/2024 16:13:21
3F：→ FRAXIS: 如果要窮舉的話大概就只能暴力解了.. 04/16 21:17