精確覆蓋矩陣和數(shù)獨(dú)-報(bào)告課件

計(jì)算機(jī)問題求解

–

論題1-8

-集合及其運(yùn)算2021年11月20日精確覆蓋問題問題的描述:GivenasetAandafinitenumberofA:A1,A2,…Ak,aexactcoverofAwithrespecttotheAi’sisasetS

{A1,A2,…Ak},satisfying:AnytwosetsinSaredisjoint,and

S=AMathematically,wecallSapartitionofA.一個(gè)例子: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

}精確覆蓋問題的矩陣表示包含關(guān)系可以用一個(gè)關(guān)系矩陣表示。矩陣每行表示S的一個(gè)子集，每列表示X中的一個(gè)元素。矩陣行列交點(diǎn)元素為1表示對應(yīng)的元素在對應(yīng)的集合中，不在那么為0例如：1234567A1001001B1001000C0001101D0010110E0110011F0100001令

S

={A,

B,

C,D,E,F}是集合X

={1,

2,

3,4,5,6,7}的一個(gè)子集，并滿足：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}便是一個(gè)精確覆蓋。精確覆蓋問題的矩陣表示Let|A|=n,andtherearemsubsetsforAi’s,wecanrepresenttheinputofexactcoverproblemasam

nmatrix,witheachrowforaAi.Solution:FindacollectionofrowsofM:r1,r2,…rk,satisfying:ri

rj=0for1i,jk,andr1

r2…rk=1where0=[0000000000]

1=[1111111111]and,isbooleanproduct,is booleansum Knuth’sXAlgorithminput:matrixAInitialization:labeltherowsofA; M=A;L={};(1)Ifthereisacolumnof0’sinM,return“Nosolution〞(2)Otherwise:Choosethecolumncwiththefewest1’s;Choosearowrwitha1incolumnc,L=L{r};Eliminateanyrowrihavingtheproperty:rri0; Eliminateallcolumnsinwhichrhasa1;Eliminaterowr;IfNorowandcolumnleft,thenoutputL,otherwiserepeat(1)and(2)onresultedM;結(jié)果是:

{A1,A3,A6,A8}舞蹈鏈〔DancingLinks〕算法——求解精確覆蓋問題DancingLinks實(shí)際上并不是一種算法，而是一種數(shù)據(jù)結(jié)構(gòu)。一種非常巧妙的數(shù)據(jù)結(jié)構(gòu)，他的數(shù)據(jù)結(jié)構(gòu)在緩存和回溯的過程中效率驚人，不需要額外的空間，以及近乎線性的時(shí)間。而在整個(gè)求解過程中，指針在數(shù)據(jù)之間跳躍著，就像精巧設(shè)計(jì)的舞蹈一樣，故DonaldE.Knuth把它稱為DancingLinks〔中文譯名舞蹈鏈〕。DancingLinks用的數(shù)據(jù)結(jié)構(gòu)是交叉十字循環(huán)雙向鏈其中的每個(gè)元素有6個(gè)分量分別：Left指向左邊的元素、Right指向右邊的元素、Up指向上邊的元素、Down指向下邊的元素、Col指向列標(biāo)元素、Row指示當(dāng)前元素所在的行

舞蹈鏈〔DancingLinks〕算法——求解精確覆蓋問題DancingLinks還要準(zhǔn)備一些輔助元素：〔1〕Ans〔〕：Ans數(shù)組，在求解的過程中保存當(dāng)前的答案，以供最后輸出答案用?！?〕Head元素：求解的輔助元素，在求解的過程中，當(dāng)判斷出Head.Right=Head〔也可以是Head.Left=Head〕時(shí)，求解結(jié)束，輸出答案。Head元素只有兩個(gè)分量有用。其余的分量對求解沒啥用〔3〕C元素：輔助元素，稱列標(biāo)元素，每列有一個(gè)列標(biāo)元素。本文開始的題目的列標(biāo)元素分別是C1、C2、C3、C4、C5、C6、C7。每一列的元素的Col分量都指向所在列的列標(biāo)元素。列標(biāo)元素的Col分量指向自己〔也可以是沒有〕。在初始化的狀態(tài)下，Head.Right=C1、C1.Right=C2、……、C7.Right=Head、Head.Left=C7等等。列標(biāo)元素的分量Row=0，表示是處在第0行。DancingLinks算法以下圖就是根據(jù)題目構(gòu)建好的交叉十字循環(huán)雙向鏈：因?yàn)榫_覆蓋問題的矩陣往往是稀疏矩陣〔矩陣中，0的個(gè)數(shù)多于1〕，DancingLinks僅僅記錄矩陣中值是1的元素?！沧⒁馐茄h(huán)的〕DancingLinks算法1、首先判斷Head.Right=Head？假設(shè)是，求解結(jié)束，輸出解；假設(shè)不是，求解還沒結(jié)束，到步驟2〔也可以判斷Head.Left=Head？〕2、獲取Head.Right元素，即元素C1，并標(biāo)示元素C1〔標(biāo)示元素C1，指的是標(biāo)示C1、和C1所在列的所有元素、以及該元素所在行的元素，并從雙向鏈中移除這些元素〕。如以下圖中的紫色局部。DancingLinks算法3、選擇行2〔在答案棧中壓入2〕，標(biāo)示該行中的其他元素〔元素5和元素6〕所在的列首元素，即標(biāo)示元素C4和標(biāo)示元素C7，以下圖中的橙色局部。注意的是，即使元素5在步驟2中就從雙向鏈中移除，但是元素5的Col分量還是指向元素C4的，這里表達(dá)了雙向鏈的強(qiáng)大作用。DancingLinks算法4、獲取Head.Right元素，即元素C2，并標(biāo)示元素C2。如以下圖中的紫色局部。DancingLinks算法5、選擇行3〔在答案棧中壓入3〕，標(biāo)示該行中的其他元素〔元素8和元素9〕所在的列首元素，即標(biāo)示元素C3和標(biāo)示元素C6，以下圖中的橙色局部。DancingLinks算法把上圖中的紫色局部和橙色局部移除的話，剩下的綠色局部就如以下圖所示。DancingLinks算法6、獲取Head.Right元素，即元素C5，元素C5中的垂直雙向鏈中沒有其他元素，也就是沒有元素覆蓋列C5。說明當(dāng)前求解失敗。要回溯到之前的分叉選擇步驟〔步驟2〕。那要回標(biāo)列首元素〔把列首元素、所在列的元素，以及對應(yīng)行其余的元素。并恢復(fù)這些元素到雙向鏈中〕，回標(biāo)列首元素的順序是標(biāo)示元素的順序的反過來。從前文可知，順序是回標(biāo)列首C6、回標(biāo)列首C3、回標(biāo)列首C2、回標(biāo)列首C7、回標(biāo)列首C4。外表上看起來比較復(fù)雜，實(shí)際上利用遞歸，是一件很簡單的事。并把答案棧恢復(fù)到步驟2〔清空的狀態(tài)〕的時(shí)候。又回到以下圖所示。DancingLinks算法7、由于之前選擇行2導(dǎo)致無解，因此這次選擇行4〔再無解就整個(gè)問題就無解了〕。選擇行4〔在答案棧中壓入4〕，標(biāo)示該行中的其他元素〔元素11〕所在的列首元素，即標(biāo)示元素C4，以下圖中的橙色局部。DancingLinks算法把上圖中的紫色局部和橙色局部移除的話，剩下的綠色局部就如以下圖所示DancingLinks算法8、獲取Head.Right元素，即元素C2，并標(biāo)示元素C2。如以下圖中的紫色局部。DancingLinks算法9、選擇行3〔在答案棧中壓入3〕，標(biāo)示該行中的其他元素〔元素8和元素9〕所在的列首元素，即標(biāo)示元素C3和標(biāo)示元素C6，以下圖中的橙色局部。DancingLinks算法把上圖中的紫色局部和橙色局部移除的話，剩下的綠色局部就如以下圖所示DancingLinks算法10、獲取Head.Right元素，即元素C5，元素C5中的垂直雙向鏈中沒有其他元素，也就是沒有元素覆蓋列C5。說明當(dāng)前求解失敗。要回溯到之前的分叉選擇步驟〔步驟8〕。從前文可知，回標(biāo)列首C6、回標(biāo)列首C3。并把答案棧恢復(fù)到步驟8〔答案棧中只有4〕的時(shí)候。又回到以下圖所示DancingLinks算法11、由于之前選擇行3導(dǎo)致無解，因此這次選擇行5〔在答案棧中壓入5〕，標(biāo)示該行中的其他元素〔元素13〕所在的列首元素，即標(biāo)示元素C7，以下圖中的橙色局部。DancingLinks算法把上圖中的紫色局部和橙色局部移除的話，剩下的綠色局部就如以下圖所示DancingLinks算法12、獲取Head.Right元素，即元素C3，并標(biāo)示元素C3。如以下圖中的紫色局部。DancingLinks算法13、如上圖，列C3只有元素1覆蓋，故答案只能選擇行3〔在答案棧壓入1〕。標(biāo)示該行中的其他元素〔元素2和元素3〕所在的列首元素，即標(biāo)示元素C5和標(biāo)示元素C6，以下圖中的橙色局部。DancingLinks算法把上圖中的紫色局部和橙色局部移除的話，剩下的綠色局部就如以下圖所示DancingLinks算法14、因?yàn)镠ead.Right=Head。故，整個(gè)過程求解結(jié)束。輸出答案，答案棧中的答案分別是4、5、1。表示該問題的解是第4、5、1行覆蓋所有的列。如以下圖所示〔藍(lán)色的局部〕DancingLinks算法從以上的14步來看，可以把DancingLinks的求解過程表述如下

1、Dancing函數(shù)的入口2、判斷Head.Right=Head？，假設(shè)是，輸出答案，返回True，退出函數(shù)。3、獲得Head.Right的元素C4、標(biāo)示元素C5、獲得元素C所在列的一個(gè)元素6、標(biāo)示該元素同行的其余元素所在的列首元素7、獲得一個(gè)簡化的問題，遞歸調(diào)用Daning函數(shù)，假設(shè)返回的True，那么返回True，退出函數(shù)。8、假設(shè)返回的是False，那么回標(biāo)該元素同行的其余元素所在的列首元素，回標(biāo)的順序和之前標(biāo)示的順序相反9、獲得元素C所在列的下一個(gè)元素，假設(shè)有，跳轉(zhuǎn)到步驟610、假設(shè)沒有，回標(biāo)元素C，返回False，退出函數(shù)。問題:你能否用集合模型描述“數(shù)獨(dú)〞〔Soduku)問題?簡單一點(diǎn)，且考慮3

3的?！皵?shù)獨(dú)〞〔Soduku)問題精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞第1列定義成：〔1，1〕填了一個(gè)數(shù)字第2列定義成：〔1，2〕填了一個(gè)數(shù)字……第9列定義成：〔1，9〕填了一個(gè)數(shù)字第10列定義成：〔2，1〕填了一個(gè)數(shù)字……第18列定義成：〔2，9〕填了一個(gè)數(shù)字……第81列定義成：〔9，9〕填了一個(gè)數(shù)字至此，用第1-81列完成了約束條件1：每個(gè)格子只能填一個(gè)數(shù)字第N列〔1≤N≤81〕定義成：〔X，Y〕填了一個(gè)數(shù)字。N、X、Y之間的關(guān)系是：N=〔X-1〕×9+Y

精確覆蓋問題與“數(shù)獨(dú)〞第82列定義成：在第1行填了數(shù)字1第83列定義成：在第1行填了數(shù)字2……第90列定義成：在第1行填了數(shù)字9第91列定義成：在第2行填了數(shù)字1……第99列定義成：在第2行填了數(shù)字9……第162列定義成：在第9行填了數(shù)字9至此，用第82-162列〔共81列〕完成了約束條件2：每行1-9的這9個(gè)數(shù)字都得填一遍第N列〔82≤N≤162〕定義成：在第X行填了數(shù)字Y。N、X、Y之間的關(guān)系是：N=〔X-1〕×9+Y+81

精確覆蓋問題與“數(shù)獨(dú)〞第163列定義成：在第1列填了數(shù)字1第164列定義成：在第1列填了數(shù)字2……第171列定義成：在第1列填了數(shù)字9第172列定義成：在第2列填了數(shù)字1……第180列定義成：在第2列填了數(shù)字9……第243列定義成：在第9列填了數(shù)字9至此，用第163-243列〔共81列〕完成了約束條件3：每列1-9的這9個(gè)數(shù)字都得填一遍第N列〔163≤N≤243〕定義成：在第X列填了數(shù)字Y。N、X、Y之間的關(guān)系是：N=〔X-1〕×9+Y+162

精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞精確覆蓋問題與“數(shù)獨(dú)〞還是舉例說明，在〔5，8〕中沒有數(shù)字把〔5，8〕中沒有數(shù)字轉(zhuǎn)換成〔5，8〕中填的是1，轉(zhuǎn)成矩陣的一行就是，第44、118、226、289列是1，其余列是0?！?，8〕中填的是2，轉(zhuǎn)成矩陣的一行就是，第44、119、227、290列是1，其余列是0?！?，8〕中填的是3，轉(zhuǎn)成矩陣的一行就是，第44、120、228、291列是1，其余列是0?！?，8〕中填的是4，轉(zhuǎn)成矩陣的一行就是，第44、121、229、292列是1，其余列是0。〔5，8〕中填的是5，轉(zhuǎn)成矩陣的一行就是，第44、122、230、293列是1，其余列是0。〔5，8〕中填的是6，轉(zhuǎn)成矩陣的一行就是，第44、123、231、294列是1，其余列是0。精確覆蓋問題與“數(shù)獨(dú)〞還是舉例說明，在〔5，8〕中沒有數(shù)字把〔5，8〕中沒有數(shù)字轉(zhuǎn)換成〔5，8〕中填的