Re: [問題] 一個關於計算最佳組合的問題
※ 引述《ephesians.bbs@ptt.cc (ephesians)》之銘言：
: ※ 引述《weijr (Beware of the Monkey)》之銘言：
: : 這是 Maximum Weight Perfect Matching
: : 你把每個板子看成一個頂點，兩個板子相連一條邊，
: : 這樣成為一個圖。然後每條邊上賦予一個 Weight=相同的標記數量。
: : 你的問題就是要找到一個 Matching 讓標記數量最多。
: : 搜尋一下網路或者找一下書，就可以找到不錯的演算法。
: 以圖的思路解決是不是有些問題呢?
: 若尋找一個解,代表從0-9這10個節點(板子)尋找一條連通路徑,
: 使其每二個一組的弧權重總和最大.
: 那想想看其中一個搜尋例子:
: 1->2--->3->4--->5->6--->7->8--->9->0
: 虛線有向弧代表雖然有弧連通,其上也有權重,但因二個一組,
: 所以虛線部份的權重不能算進來.
: 另有個想法是,將所有的板子做成配對計分矩陣,每一格儲存non-match數目:
: 0 1 2 3 4 5 6 7 8 9
: 0 0 5 2 1 10 25 18 3 5 2
: 1 0 1 3 20 14 11 9 17 5
: 2 0 10 9 18 18 20 35 1
: 3 ...
: 這個矩陣會對稱,因為(i,j)的non-match與(j,i)的一樣.
: 於是搜尋空間可縮小於右上半邊,或左下半邊.
: 在搜尋空間中,做 n/2 rook quiz的解決.
: 曾經看過用backtracking技巧解決 8 queen quiz,
: 用類似的方法,可以讓n/2 rook quiz做得快.
這個問題確實與 Maximum/Minimum Weight Perfect Matching 相同，
用路徑搜尋的解法也只要 O(V^2 *logV + VE) 次，
對於一個只有 70 片 (V = 70) 的 case，
大概花不到兩秒鐘就算完了。
這個問題有標準解法，B 開頭的，
網路上有各種論文有更快的解法，
請加油。
--
〒作者：zsexdrcf 來自：ipvr4.csie.ncu.edu.tw
◎二進位的世界【140.115.50.50‧bbs.ncu.cc】
推
04/24 14:23, , 1F
04/24 14:23, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：