Re: [問題] 一個關於計算最佳組合的問題
看板Programming作者weijr (Beware of the Monkey)時間17年前 (2007/04/20 13:14)推噓1(1推 0噓 1→)留言2則, 1人參與討論串4/6 (看更多)
※ 引述《ling123 (@@)》之銘言：
: 首先非常感謝你的回答~
: 板子通常會被區分成100~200個區域
: 一次會有50~70片~
: 我們是想運用在當兩個產品組合時~
: 讓有相同問題的板子盡量放在一起~以減少報廢品
: 我們現在遇到的問題是~要是以嘗試所有組合來算出最佳解當出發點的話
: 這樣花的時間難以估計()~也不符合成本效益~
: 所以想要看看有沒有可能以資料結構或演算法來求最佳解~
這是 Maximum Weight Perfect Matching
你把每個板子看成一個頂點，兩個板子相連一條邊，
這樣成為一個圖。然後每條邊上賦予一個 Weight=相同的標記數量。
你的問題就是要找到一個 Matching 讓標記數量最多。
搜尋一下網路或者找一下書，就可以找到不錯的演算法。
--
http://weijr-note.blogspot.com 筆記筆記
http://weijr.b81.org/poker 好膽玩家
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 134.208.26.237
推
04/21 02:19, , 1F
04/21 02:19, 1F
→
04/21 02:22, , 2F
04/21 02:22, 2F
討論串 (同標題文章)