Re: [問題] 一個關於計算最佳組合的問題
※ 引述《weijr (Beware of the Monkey)》之銘言：
: ※ 引述《ling123 (@@)》之銘言：
: : 首先非常感謝你的回答~
: : 板子通常會被區分成100~200個區域
: : 一次會有50~70片~
: : 我們是想運用在當兩個產品組合時~
: : 讓有相同問題的板子盡量放在一起~以減少報廢品
: : 我們現在遇到的問題是~要是以嘗試所有組合來算出最佳解當出發點的話
: : 這樣花的時間難以估計()~也不符合成本效益~
: : 所以想要看看有沒有可能以資料結構或演算法來求最佳解~
: 這是 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做得快.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.210.54
討論串 (同標題文章)