推 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
→ 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
→ FRAXIS: 如果要窮舉的話大概就只能暴力解了.. 04/16 21:17