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

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

看板Prob_Solve (計算數學 Problem Solving)作者petingo (皮挺哥)時間8月前 (2024/04/10 15:45)推噓3(3推 0噓 2→)

留言5則, 3人參與討論串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

推

LPH66

04/10 19:18, 8月前 , 1^F

04/10 19:18, 1^F

對！原來這東西叫 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

04/12 03:49, 8月前 , 2^F

04/12 03:49, 2^F

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