※ 引述《[email protected] (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】