精确覆盖矩阵和数独-报告PPT课件.ppt

问题: 你能否用集合模型描述“数独”（Soduku)问题? 简单一点，且考虑3?3的。 数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复 “数独”（Soduku)问题 计算机问题求解 – 论题1-8 - 集合及其运算 2012年11月20日 精确覆盖问题 问题的描述: Given a set A and a finite number of A: A1,A2,…Ak, a exact cover of A with respect to the Ai’s is a set S? {A1,A2,…Ak} , satisfying: Any two sets in S are disjoint, and ?S=A Mathematically, we call S a partition of A. 一个例子: A={a,b,c,d,e,f,g,h,i,j}; A1={a,c,d}, A2={a,b,e,f}, A3={b,f,g}, A4={d,h,i }, A5={a,h,j}, A6={e,h}, A7={c,i,j}, A8={i,j} 解是： {A1, A3, A6, A8 } 精确覆盖问题的矩阵表示 包含关系可以用一个关系矩阵表示。矩阵每行表示S的一个子集，每列表示X中的一个元素。矩阵行列交点元素为1表示对应的元素在对应的集合中，不在则为0 例如： 1 2 3 4 5 6 7 A 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 E 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1 令? S?= {A,?B,?C,D,E,F} 是集合X?= { 1,?2,?3,4,5,6,7}的一个子集，并满足： A?= {1,4,7 } B= {1, 4} C?= {4, 5,7} D?= {3, 5,6} E = {2,3, 6,7} F= {2,7} S* = {B,?D,?F} 便是一个精确覆盖。 精确覆盖问题的矩阵表示 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）算法——求解精确覆盖问题 Dancing Links实际上并不是一种算法，而是一种数据结构。一种非常巧妙的数据结构，他的数据结构在缓存和回溯的过程中效率惊人，不需要额外的空间，以及近乎线性