精确覆盖矩阵和其数独 - 报告ppt.ppt

问题: 你能否用集合模型描述“数独”（Soduku)问题? 简单一点，且考虑3?3的。 数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复 “数独”（Soduku)问题 计算机问题求解 – 论题1-8 - 集合及其运算 2012年11月20日 精确覆盖问题的矩阵表示 Let |A|=n, and there are m subsets for Ai’s, we can represent the input of exact cover problem as a m?n matrix, with each row for a Ai . Solution: Find a collection of rows of M: r1, r2,…rk, satisfying: ri?rj=0 for 1?i,j?k, and r1?r2?…?rk=1 where 0=[0 0 0 0 0 0 0 0 0 0] 1=[1 1 1 1 1 1 1 1 1 1] and, ? is boolean product, ? is boolean sum Knuth’s X Algorithm input: matrix A Initialization: label the rows of A; M=A; L={}; (1) If there is a column of 0’s in M, return “No solution” (2) Otherwise: Choose the column c with the fewest 1’s; Choose a row r with a 1 in column c, L=L?{r}; Eliminate any row ri having the property: r?ri?0; Eliminate all columns in which r has a 1; Eliminate row r; If No row and column left, then output L, otherwise repeat (1) and (2) on resulted M; 结果是: { A1, A3, A6, A8 } 舞蹈链（Dancing Links）算法——求解精确覆盖问题 回溯 对于原始矩阵来说解集合（第1、4、5行） 舞蹈链（Dancing Links）算法——求解精确覆盖问题 在求解这个问题的过程中，我们第1步选择第1行是正确的，但是不是每个题目第1步选择都是正确的，如果选择第1行无法求解出结果出来，那么就要推倒之前的选择，从选择第2行开始，以此类推。 从上面的求解过程来看，实际上求解过程可以如下表示： 1、从矩阵中选择一行 2、根据定义，标示矩阵中其他行的元素 3、删除相关行和列的元素，得到新矩阵 4、如果新矩阵是空矩阵，并且之前的一行都是1，那么求解结束，跳转到6；新矩阵不是空矩阵，继续求解，跳转到1；新矩阵是空矩阵，之前的一行中有0，跳转到5 5、说明之前的选择有误，回溯到之前的一个矩阵，跳转到1；如果没有矩阵可以回溯，说明该问题无解，跳转到7 6、求解结束，把结果输出 7、求解结束，输出无解消息 舞蹈链（Dancing Links）算法——求解精确覆盖问题 Dancing Links实际上并不是一种算法，而是一种数据结构。一种非常巧妙的数据结构，他的数据结构在缓存和回溯的过程中效率惊人，不需要额外的空间，以及近乎线性的时间。而在整个求解过程中，指针在数据之间跳跃着，就像精巧设计的舞蹈一样，故Donald E.Knuth把它称为Dancing Links（中文译名舞蹈链）。 Dancing Links用的数据结构是交叉十字循环双向链其中的每个元素有6个分量分别：Left指向左边的元素、Right指向右边的元素、Up指向上边的元素、Down指向下边的元素、Col指向列标元素、Row指示当前元素所在的行 ? 舞蹈链（Dancing Links）算法——求解精确覆盖问题 Dancing Links还要准备一些辅助元素： （1）Ans（）：Ans数组，在求解的过程中保留当前的答案，以供最后输出答案用。 （2）Head元素：求解的辅助元素，在求解的过程中，当判断出Head.Right=Head（也可以是Head.Left=Head）时，求解结束，输出答案。Head元素只有两个分量有用。其余的分量对求解没啥用 （3）C元素