《精确覆盖矩阵和数独报告ppt课件》由会员分享，可在线阅读，更多相关《精确覆盖矩阵和数独报告ppt课件（45页珍藏版）》请在金锄头文库上搜索。
1、计算机问题求解 论题1-8 - 集合及其运算2021年11月20日准确覆盖问题n问题的描画:nGivenasetAandafinitenumberofA:A1,A2,Ak,aexactcoverofAwithrespecttotheAisisasetSA1,A2,Ak,satisfying:nAnytwosetsinSaredisjoint,andnS=AnMathematically,wecallSapartitionofA.n一个例子:nA=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,A
2、7=c,i,j,A8=i,jn解是：A1,A3,A6,A8准确覆盖问题的矩阵表示包含关系可以用一个关系矩阵表示。矩阵每行表示S的一个子集，每列表示X中的一个元素。矩阵行列交点元素为1表示对应的元素在对应的集合中，不在那么为0例如：1 12 23 34 45 56 67 7A A 1 0 0 1 0 0 1B B 1 1 0 0 1 1 0 0 0C C 0 0 0 1 1 0 1D D 0 0 1 1 0 1 1 1 1 0E E 0 1 1 0 0 1 1F F 0 1 1 0 0 0 0 1 1令S=A,B,C,D,E,F是集合X=1,2,3,4,5,6,7的一个子集，并满足：A=1,4,
3、7B=1,4C=4,5,7D=3,5,6E=2,3,6,7F=2,7S*=B,D,F便是一个准确覆盖。准确覆盖问题的矩阵表示Let|A|=n,andtherearemsubsetsforAis,wecanrepresenttheinputofexactcoverproblemasamnmatrix,witheachrowforaAi.Solution:FindacollectionofrowsofM:r1,r2,rk,satisfying:rirj=0for1i,jk,andr1r2rk=1where0=00000000001=1111111111and,isbooleanproduct,is
4、booleansumKnuthsXAlgorithmninput: matrix AnInitialization: label the rows of A;n M=A; L=;n(1) If there is a column of 0s in M, return “No solutionn(2) Otherwise:nChoose the column c with the fewest 1s;nChoose a row r with a 1 in column c, L=Lr;nEliminate any row ri having the property: rri0;nElimina
5、te all columns in which r has a 1;nEliminate row r;nIf No row and column left, then output L, otherwise repeat (1) and (2) on resulted M;结果是: A1, A3, A6, A8 舞蹈舞蹈链Dancing Links算法算法求解准确覆盖求解准确覆盖问题DancingLinks实践上并不是一种算法，而是一种数据构造。一种非常巧妙的数据构造，他的数据构造在缓存和回溯的过程中效率惊人，不需求额外的空间，以及近乎线性的时间。而在整个求解过程中，指针在数据之间腾跃着，就像
6、精巧设计的舞蹈一样，故DonaldE.Knuth把它称为DancingLinks中文译名舞蹈链。DancingLinks用的数据构造是交叉十字循环双向链其中的每个元素有6个分量分别：Left指向左边的元素、Right指向右边的元素、Up指向上边的元素、Down指向下边的元素、Col指向列标元素、Row指示当前元素所在的行舞蹈舞蹈链Dancing Links算法算法求解准确覆盖求解准确覆盖问题DancingLinks还要预备一些辅助元素：1Ans：Ans数组，在求解的过程中保管当前的答案，以供最后输出答案用。2Head元素：求解的辅助元素，在求解的过程中，当判别出Head.Right=Head也
7、可以是Head.Left=Head时，求解终了，输出答案。Head元素只需两个分量有用。其他的分量对求解没啥用3C元素：辅助元素，称列标元素，每列有一个列标元素。本文开场的标题的列标元素分别是C1、C2、C3、C4、C5、C6、C7。每一列的元素的Col分量都指向所在列的列标元素。列标元素的Col分量指向本人也可以是没有。在初始化的形状下，Head.Right=C1、C1.Right=C2、C7.Right=Head、Head.Left=C7等等。列标元素的分量Row=0，表示是处在第0行。Dancing Links算法算法以下图就是根据标题构建好的交叉十字循环双向链：由于准确覆盖问题的矩阵往
8、往是稀疏矩阵矩阵中，0的个数多于1，DancingLinks仅仅记录矩阵中值是1的元素。留意是循环的Dancing Links算法算法1、首先判别Head.Right=Head？假设是，求解终了，输出解；假设不是，求解还没终了，到步骤2也可以判别Head.Left=Head？2、获取Head.Right元素，即元素C1，并标示元素C1标示元素C1，指的是标示C1、和C1所在列的一切元素、以及该元素所在行的元素，并从双向链中移除这些元素。如以下图中的紫色部分。Dancing Links算法算法3、选择行2在答案栈中压入2，标示该行中的其他元素元素5和元素6所在的列首元素，即标示元素C4和标示元素
9、C7，以下图中的橙色部分。留意的是，即使元素5在步骤2中就从双向链中移除，但是元素5的Col分量还是指向元素C4的，这里表达了双向链的强大作用。Dancing Links算法算法4、获取Head.Right元素，即元素C2，并标示元素C2。如以下图中的紫色部分。Dancing Links算法算法5、选择行3在答案栈中压入3，标示该行中的其他元素元素8和元素9所在的列首元素，即标示元素C3和标示元素C6，以下图中的橙色部分。Dancing Links算法算法把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如以下图所示。Dancing Links算法算法6、获取Head.Right元素，即元
10、素C5，元素C5中的垂直双向链中没有其他元素，也就是没有元素覆盖列C5。阐明当前求解失败。要回溯到之前的分叉选择步骤步骤2。那要回标列首元素把列首元素、所在列的元素，以及对应行其他的元素。并恢复这些元素到双向链中，回标列首元素的顺序是标示元素的顺序的反过来。从前文可知，顺序是回标列首C6、回标列首C3、回标列首C2、回标列首C7、回标列首C4。外表上看起来比较复杂，实践上利用递归，是一件很简单的事。并把答案栈恢复到步骤2清空的形状的时候。又回到以下图所示。Dancing Links算法算法7、由于之前选择行2导致无解，因此这次选择行4再无解就整个问题就无解了。选择行4在答案栈中压入4，标示该行
11、中的其他元素元素11所在的列首元素，即标示元素C4，以下图中的橙色部分。Dancing Links算法算法把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如以下图所示Dancing Links算法算法8、获取Head.Right元素，即元素C2，并标示元素C2。如以下图中的紫色部分。Dancing Links算法算法9、选择行3在答案栈中压入3，标示该行中的其他元素元素8和元素9所在的列首元素，即标示元素C3和标示元素C6，以下图中的橙色部分。Dancing Links算法算法把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如以下图所示Dancing Links算法算法10、获取H
12、ead.Right元素，即元素C5，元素C5中的垂直双向链中没有其他元素，也就是没有元素覆盖列C5。阐明当前求解失败。要回溯到之前的分叉选择步骤步骤8。从前文可知，回标列首C6、回标列首C3。并把答案栈恢复到步骤8答案栈中只需4的时候。又回到以下图所示Dancing Links算法算法11、由于之前选择行3导致无解，因此这次选择行5在答案栈中压入5，标示该行中的其他元素元素13所在的列首元素，即标示元素C7，以下图中的橙色部分。Dancing Links算法算法把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如以下图所示Dancing Links算法算法12、获取Head.Right元素
13、，即元素C3，并标示元素C3。如以下图中的紫色部分。Dancing Links算法算法13、如上图，列C3只需元素1覆盖，故答案只能选择行3在答案栈压入1。标示该行中的其他元素元素2和元素3所在的列首元素，即标示元素C5和标示元素C6，以下图中的橙色部分。Dancing Links算法算法把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如以下图所示Dancing Links算法算法14、由于Head.Right=Head。故，整个过程求解终了。输出答案，答案栈中的答案分别是4、5、1。表示该问题的解是第4、5、1行覆盖一切的列。如以下图所示蓝色的部分Dancing Links算法算法从以
14、上的14步来看，可以把DancingLinks的求解过程表述如下1、Dancing函数的入口2、判别Head.Right=Head？，假设是，输出答案，前往True，退出函数。3、获得Head.Right的元素C4、标示元素C5、获得元素C所在列的一个元素6、标示该元素同行的其他元素所在的列首元素7、获得一个简化的问题，递归调用Daning函数，假设前往的True，那么返回True，退出函数。8、假设前往的是False，那么回标该元素同行的其他元素所在的列首元素，回标的顺序和之前标示的顺序相反9、获得元素C所在列的下一个元素，假设有，跳转到步骤610、假设没有，回标元素C，前往False，退出
15、函数。问题:他能否用集合模型描他能否用集合模型描画画“数独数独Soduku)问题?简单一点，且思索33的。数独Sudoku是一种运用纸、笔进展演算的逻辑游戏。玩家需求根据99盘面上的知数字，推理出一切剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不反复“数独数独Soduku)问题准确覆盖问题与“数独n那利用舞蹈链DancingLinks算法求解数独问题，实践上就是下面一个流程：n把数独问题转换为准确覆盖问题n设计出数据矩阵n用舞蹈链DancingLinks算法求解该准确覆盖问题n把该准确覆盖问题的解转换为数独的解n首先看看数独问题9*9的方格的规那么：n每个格子只能填一
16、个数字n每行每个数字只能填一遍n每列每个数字只能填一遍n每宫每个数字只能填一遍准确覆盖问题与“数独n在把数独问题转换为准确覆盖问题时把行当做是形状，把在把数独问题转换为准确覆盖问题时把行当做是形状，把列当做是需求满足的条件。列当做是需求满足的条件。n 那如今就是利用这个规那么把数独问题转换为准确覆那如今就是利用这个规那么把数独问题转换为准确覆盖问题可是，直观上面的规那么，发现比较难以转换为准盖问题可是，直观上面的规那么，发现比较难以转换为准确覆盖问题。因此，把上面的表述换个说法：确覆盖问题。因此，把上面的表述换个说法：n每个格子只能填一个数字每个格子只能填一个数字n每行每行1-9的这的这9个数
17、字都得填一遍也就意味着每个数字只个数字都得填一遍也就意味着每个数字只能填一遍能填一遍n每列每列1-9的这的这9个数字都得填一遍个数字都得填一遍n每宫每宫1-9的这的这9个数字都得填一遍个数字都得填一遍n 我们把矩阵的每个列都定义成一个约束条件：我们把矩阵的每个列都定义成一个约束条件：准确覆盖问题与“数独n第1列定义成：1，1填了一个数字n第2列定义成：1，2填了一个数字nn第9列定义成：1，9填了一个数字n第10列定义成：2，1填了一个数字nn第18列定义成：2，9填了一个数字nn第81列定义成：9，9填了一个数字n至此，用第1-81列完成了约束条件1：每个格子只能填一个数字n第N列1N81定
18、义成：X，Y填了一个数字。nN、X、Y之间的关系是：N=X-19+Yn准确覆盖问题与“数独n第82列定义成：在第1行填了数字1n第83列定义成：在第1行填了数字2nn第90列定义成：在第1行填了数字9n第91列定义成：在第2行填了数字1nn第99列定义成：在第2行填了数字9nn第162列定义成：在第9行填了数字9n至此，用第82-162列共81列完成了约束条件2：每行1-9的这9个数字都得填一遍n第N列82N162定义成：在第X行填了数字Y。nN、X、Y之间的关系是：N=X-19+Y+81n准确覆盖问题与“数独n第163列定义成：在第1列填了数字1n第164列定义成：在第1列填了数字2nn第1
19、71列定义成：在第1列填了数字9n第172列定义成：在第2列填了数字1nn第180列定义成：在第2列填了数字9nn第243列定义成：在第9列填了数字9n至此，用第163-243列共81列完成了约束条件3：每列1-9的这9个数字都得填一遍n第N列163N243定义成：在第X列填了数字Y。nN、X、Y之间的关系是：N=X-19+Y+162n准确覆盖问题与“数独n第244列定义成：在第1宫填了数字1n第245列定义成：在第1宫填了数字2nn第252列定义成：在第1宫填了数字9n第253列定义成：在第2宫填了数字1nn第261列定义成：在第2宫填了数字9nn第324列定义成：在第9宫填了数字9n至此，
20、用第244-324列共81列完成了约束条件4：每宫1-9的这9个数字都得填一遍n第N列244N324定义成：在第X宫填了数字Y。nN、X、Y之间的关系是：N=X-19+Y+243准确覆盖问题与“数独n第244列定义成：在第1宫填了数字1n第245列定义成：在第1宫填了数字2nn第252列定义成：在第1宫填了数字9n第253列定义成：在第2宫填了数字1nn第261列定义成：在第2宫填了数字9nn第324列定义成：在第9宫填了数字9n至此，用第244-324列共81列完成了约束条件4：每宫1-9的这9个数字都得填一遍n第N列244N324定义成：在第X宫填了数字Y。nN、X、Y之间的关系是：N=X
21、-19+Y+243准确覆盖问题与“数独n第244列定义成：在第1宫填了数字1n第245列定义成：在第1宫填了数字2nn第252列定义成：在第1宫填了数字9n第253列定义成：在第2宫填了数字1nn第261列定义成：在第2宫填了数字9nn第324列定义成：在第9宫填了数字9n至此，用第244-324列共81列完成了约束条件4：每宫1-9的这9个数字都得填一遍n第N列244N324定义成：在第X宫填了数字Y。nN、X、Y之间的关系是：N=X-19+Y+243准确覆盖问题与“数独n至此，用了324列完成了数独的四个约束条件，矩阵的列定义完成。那接下来，就是把数独转换为矩阵数独问题中，每个格子分两种情
22、况：n有数字格子n以例子来阐明，在4，2中填的是7n把4，2中填的是7，解释成4个约束条件n1、在4，2中填了一个数字。n2、在第4行填了数字7n3、在第2列填了数字7n4、在第4宫填了数字7坐标X，Y到宫N的公式为：N=INTX-1/33+INTY-1/3+1nn没数字的格子准确覆盖问题与“数独那么这4个条件，分别转换成矩阵对应的列为1、在4，2中填了一个数字。对应的列N=4-19+2=292、在第4行填了数字7。对应的列N=4-19+7+81=1153、在第2列填了数字7。对应的列N=2-19+7+162=1784、在第4宫填了数字7。对应的列N=4-19+7+243=277于是，4，2中
23、填的是7，转成矩阵的一行就是，第29、115、178、277列是1，其他列是0。把这1行插入到矩阵中去。没数字的格子准确覆盖问题与“数独还是举例阐明，在5，8中没有数字把5，8中没有数字转换成5，8中填的是1，转成矩阵的一行就是，第44、118、226、289列是1，其他列是0。5，8中填的是2，转成矩阵的一行就是，第44、119、227、290列是1，其他列是0。5，8中填的是3，转成矩阵的一行就是，第44、120、228、291列是1，其他列是0。5，8中填的是4，转成矩阵的一行就是，第44、121、229、292列是1，其他列是0。5，8中填的是5，转成矩阵的一行就是，第44、122、2
24、30、293列是1，其他列是0。5，8中填的是6，转成矩阵的一行就是，第44、123、231、294列是1，其他列是0。准确覆盖问题与“数独还是举例阐明，在5，8中没有数字把5，8中没有数字转换成5，8中填的是1，转成矩阵的一行就是，第44、118、226、289列是1，其他列是0。5，8中填的是2，转成矩阵的一行就是，第44、119、227、290列是1，其他列是0。5，8中填的是3，转成矩阵的一行就是，第44、120、228、291列是1，其他列是0。5，8中填的是4，转成矩阵的一行就是，第44、121、229、292列是1，其他列是0。5，8中填的是5，转成矩阵的一行就是，第44、122
25、、230、293列是1，其他列是0。5，8中填的是6，转成矩阵的一行就是，第44、123、231、294列是1，其他列是0。准确覆盖问题与“数独5，8中填的是7，转成矩阵的一行就是，第44、124、232、295列是1，其他列是0。5，8中填的是8，转成矩阵的一行就是，第44、125、233、296列是1，其他列是0。5，8中填的是9，转成矩阵的一行就是，第44、126、234、297列是1，其他列是0。把这9行插入到矩阵中。由于这9行的第44列都是1不会有其他行的44列会是1，也就是说这9行中必只需1行有且只需1行选中准确覆盖问题的定义，每列只能有1个1，是最后解的一部分。这就保证了最后解在5，8中只需1个数字。这样，从数独的格子依次转换成行1行或者9行插入到矩阵中。完成了数独问题到准确覆盖问题的转换。接下来我们就可以用舞蹈链DancingLinks算法求解该准确覆盖问题最终利用N,X,Y的公式求解数独问题空白处的数字。
