※ 引述《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