算法導(dǎo)論復(fù)習(xí)資料

1、.算法導(dǎo)論復(fù)習(xí)資料一、選擇題：第一章的概念、術(shù)語。二、考點(diǎn)分析：1、復(fù)雜度的漸進(jìn)表示，復(fù)雜度分析。2、正確性證明?？键c(diǎn)： 1）正確性分析（冒泡，歸并，選擇） ； 2）復(fù)雜度分析（漸進(jìn)表示 O， ? ，替換法證明，先猜想，然后給出遞歸方程） 。循環(huán)不變性的三個(gè)性質(zhì)：1）初始化：它在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的；2）保持：如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應(yīng)該保持正確；3）當(dāng)循環(huán)結(jié)束時(shí)，不變式給了我們一個(gè)有用的性質(zhì)，它有助于表明算法是正確的。插入排序算法：INSERTION-SORT(A)1 for j 2 to lengthA2 do key A

2、j3? Insert Aj into the sorted sequence A1 ， j - 1.4i j - 15while i > 0 and Ai > key6do Ai + 1 Ai7i i - 18Ai + 1 key插入排序的正確性證明：課本11頁。歸并排序算法：課本17頁及 19頁。歸并排序的正確性分析：課本20頁。3、分治法（基本步驟，復(fù)雜度分析）。許多問題都可以遞歸求解考點(diǎn)：快速排序，歸并排序，漸進(jìn)排序，例如： 12 球里面有一個(gè)壞球，怎樣用最少的次數(shù)找出來。（解：共有 24種狀態(tài)，至少稱重 3次可以找出不同的球）不是考點(diǎn)：線性時(shí)間選擇，最接近點(diǎn)對(duì)，斯特拉算法求

3、解。解：基本步驟：一、分解：將原問題分解成一系列的子問題；二、解決：遞歸地解各子問題。若子問題足夠小，則直接求解；三、合并：將子問題的結(jié)果合并成原問題的解。復(fù)雜度分析：分分治算法中的遞歸式是基于基本模式中的三個(gè)步驟的， T(n)為一個(gè)規(guī)模為 n的運(yùn)行時(shí)間，得到遞歸式T(n)=Q(1)n<=cT(n)=aT(n/b)+D(n)+C(n)n>c附加習(xí)題：請(qǐng)給出一個(gè)運(yùn)行時(shí)間為 Q(nlgn) 的算法，使之能在給定的一個(gè)由 n 個(gè)整數(shù)構(gòu)成的集合 S 和另一個(gè)整數(shù) x時(shí)，判斷出 S中是否存在有兩個(gè)其和等于 x的元素。Word 資料.Word 資料.4、動(dòng)態(tài)規(guī)劃（最優(yōu)子結(jié)構(gòu)性質(zhì)，自底向上填表計(jì)

4、算最優(yōu)解值（即最長公共子序列），導(dǎo)出最優(yōu)解）?？键c(diǎn)：最優(yōu)子結(jié)構(gòu)性質(zhì)，自底向上填表計(jì)算最優(yōu)解值，導(dǎo)出最優(yōu)解。a）動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的 4個(gè)步驟： 1 ）描述最優(yōu)解的結(jié)構(gòu)；2）遞歸定義最優(yōu)解的值； 3）按自底向上的方式計(jì)算最優(yōu)解的值；4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解。b ）最優(yōu)子結(jié)構(gòu)遵循的共同模式：1 ）問題的一個(gè)解可以是做一個(gè)選擇，做這種選擇可能會(huì)得到一個(gè)或多個(gè)有待解決的子問題；2）假設(shè)對(duì)一個(gè)給定的問題， 已知的是一個(gè)可以導(dǎo)致最優(yōu)解的選擇，不必關(guān)心如何確定這個(gè)選擇，盡管假定它是已知的；3）在已知這個(gè)選擇后，要確定哪些子問題會(huì)隨之發(fā)生， 以及如何最好地描述所得到的子問題的空間；4 ）利用一種 “剪切

5、粘貼法 ”，來證明在問題的一個(gè)最優(yōu)解中，使用的子問題的解本身也必須是最優(yōu)的。備注： Aproblemexhibits optimal substructureif an optimal solutionto theproblemcontainswithin itoptimal solutions to subproblems.Word 資料.Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply.c）最長公共子序列的算法：這里以兩個(gè)序列 X=x1

6、,x2, ,xm和 Y=y1,y2, ,yn為輸入，注意課本211頁的自底向上填表方法。LCS-LENGTH(X, Y)注：此程序運(yùn)行時(shí)間為O（ mn ），每個(gè)表項(xiàng)的計(jì)算時(shí)間為O（ 1）1 m lengthX2 n lengthY3 for i 1 to m4 do ci, 0 05 for j 0 to n6 do c0, j 07 for i 1 to m8do for j 1 to n9do ifxi = yj10thenci, j ci - 1, j - 1 + 111bi, j “="12else if ci - 1, j ci, j - 113then ci, j ci

7、- 1, j14bi, j ""15elseci, j ci, j - 116bi, j " "17 returnc and bPRINT-LCS(b, X, i, j)注：此程序運(yùn)行時(shí)間為O（ m+n ）1 if i = 0 or j = 02 then return3 if bi, j = "="4 then PRINT-LCS(b, X, i - 1, j - 1)5print xi6elseifbi, j = " "7then PRINT-LCS(b, X, i - 1, j)8else PRINT-LCS

8、(b, X, i, j - 1)d ）矩陣鏈乘法的算法：參照課本上的矩陣鏈表得出矩陣相乘的最小算法。m i , j m in mi , k m k1, j ikjpi 1 pk p j MATRIX-CHAIN-ORDER(p)每個(gè)表項(xiàng)的復(fù)雜度是O（ n ），共有 O（ n2 ）表項(xiàng)，則為O（n3 ）1 n lengthp - 12 for i 1 to nWord 資料.3do mi, i 04for l 2 ton ? l is the chain length.5do fori 1 ton - l + 16do j i + l - 17mi, j 8for k i to j - 19do

9、q mi, k + mk + 1, j + pi-1 pkpj10if q < mi, j11then mi, j q12si, j k13return m and sPRINT-OPTIMAL-PARENS(s, i, j)1ifi = j2then print "Ai "3else print "("4PRINT-OPTIMAL-PARENS(s, i, si, j)5PRINT-OPTIMAL-PARENS(s, si, j + 1, j)6 print ")"e）備忘錄算法： 1）程序結(jié)構(gòu)采用自頂向上； 2）保留了遞歸結(jié)

10、構(gòu)，開銷較大； 3）當(dāng)所有的子問題都需要求解時(shí)，自底向上的方法效率較高，否則可以采用備忘錄方法。備忘錄算法的代碼可以參照課本207 頁。f）最優(yōu)二叉查找樹：1 ）一棵最優(yōu)二叉查找樹不一定是一棵整體高度最小的樹，也不一定總是把有最大概率的關(guān)鍵字放在根部來構(gòu)造一棵最優(yōu)二叉查找樹。5、貪心法（最優(yōu)子結(jié)構(gòu)性質(zhì)+ 貪心選擇性質(zhì)） ?？键c(diǎn)：學(xué)會(huì)證明最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)的問題。a）活動(dòng)選擇問題：0ifSijci , j maxikj ci ,k c k, j 1ifSij注意課本上 224頁地貪婪法定理證明，這就是貪婪法的合理性證明。RECURSIVE-ACTIVITY-SELECTOR(s, f,

11、 i, j)1 m i + 12 while m < j and sm < fi?Find the first activity in Sij.3 do m m + 14 if m < j5then returnam RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)6 else returnGREEDY-ACTIVITY-SELECTOR(s, f)1 n lengths2 A a1Word 資料.3 i 1 24 for m 2 to n5do if sm fi6then A A am7i m8 returnAb ）貪心算法遵循的步驟：1）決定

12、問題的最優(yōu)子結(jié)構(gòu)；2 ）設(shè)計(jì)出一個(gè)遞歸解；3）證明在遞歸的任一階段，最優(yōu)選擇之一總是貪心選擇，那么，做貪心選擇總是安全的；4）證明通過做貪心選擇，所有的子問題（出一個(gè)以外）都為空；5 ）設(shè)計(jì)出一個(gè)實(shí)現(xiàn)貪心策略的遞歸算法；6）將遞歸算法轉(zhuǎn)換成迭代算法。c）根據(jù)貪心選擇來構(gòu)造最優(yōu)子結(jié)構(gòu)：1）將優(yōu)化問題轉(zhuǎn)化成這樣一個(gè)問題，即先做出選擇，再解決剩下的一個(gè)子問題；2）證明原問題總是有一個(gè)最優(yōu)解是做貪心選擇得到的，從而說明貪心選擇的安全； 3）說明在做貪心選擇后，剩余的子問題具有這樣的一個(gè)性質(zhì)，即如果將子問題的最優(yōu)解和我們所作的貪心選擇聯(lián)合起來，可以得出原問題的一個(gè)最優(yōu)解。d ）貪心選擇性質(zhì)：證明定理 1

13、6.1e）最優(yōu)子結(jié)構(gòu)性質(zhì)：課本229頁。6、搜索（回溯法、剪枝函數(shù)、最小成本優(yōu)先）。考點(diǎn)：回溯，剪枝函數(shù)，最小成本優(yōu)先的問題；分支界限法，剪枝函數(shù)所具備的性質(zhì)。a）回溯法：1）定義：回溯法(探索與回溯法 )是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn) ”。2）回溯法解題的步驟：a、針對(duì)所給的問題，定義問題的解空間；b 、確定易于搜索的解空間結(jié)構(gòu)；c、以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。2）回溯法解決的n后問題：在一

14、個(gè)n * n 的棋盤上放置n個(gè)王后，使得n后彼此不受攻擊。3 ）回溯法解決 0-1 背包問題：附：證明部分背包問題具有貪心選擇性質(zhì)。課本練習(xí)題 16.2-3 ：Word 資料.c 剪枝函數(shù)：約束函數(shù)：剪去不滿足約束函數(shù)的子樹；限界函數(shù)：剪去由限界函數(shù)表明不能得到最優(yōu)解的子樹。P( x1 , x2 ,., xk 1) P( x1 , x2 ,.,xk )0k剪枝函數(shù)的必要條件：典型例題： 1）求不等式的整數(shù)解5x1+4x 2x32 ）裝載問題：c）最小成本優(yōu)先算法：注：分支限界的基本思想：1回溯法的深度優(yōu)先比較盲目2廣度優(yōu)先代價(jià)太高4 能優(yōu)先搜索那些最有希望得到解的路徑6 深入分析問題，得到有用

15、的啟發(fā)信息n10, 1xj3, i =1,2,3Word 資料.7 利用啟發(fā)信息構(gòu)造成本函數(shù)8 最小成本優(yōu)先的搜索策略9 結(jié)合剪枝函數(shù)典型題型：重拍九宮問題。7、最大流（概念，最大流- 最小割定理，Edmonds-Karp算法）?？键c(diǎn)：最大流的相關(guān)概念， 最大流 最小割定理， Edmonds-Karp 算法，要求掌握 Ford-Fulkerson 算法的相關(guān)容。1）流網(wǎng)絡(luò)定義：有向圖G = ( V, E)，如果圖 G滿足：存在源結(jié)點(diǎn) (source) s（ s的入度為 0）存在匯結(jié)點(diǎn) (sink) t（ t的出度為 0）任意結(jié)點(diǎn) v V，有 s v t+容量函數(shù)C： E R流的定義：流網(wǎng)絡(luò)G，

16、若函數(shù)p： V XV R+ 滿足下述條件：容量限制：對(duì)任意(u,v) E，有 0<=p(u,v)<=c(u,v)守恒條件：對(duì)任意u (V-s,t) ，有則稱 p為 G上的流。注意課本 399 頁的引理。2）對(duì)源點(diǎn)頂點(diǎn)來說，離開它的正流要比進(jìn)入它的正流更多；對(duì)匯點(diǎn)頂點(diǎn)來說，進(jìn)入它的正流要比離開它的正流更多。先證明如下： |f|=f （ s， V）=f （ V， V） -f （ V-s ， V）=f （ V， V-s ）=f （ V， t ） +f （ V， V-s-t ）=f （ V， t ）3）Ford-Fulkerson 方法：此方法依賴三中重要思想，a、殘留網(wǎng)絡(luò)； b 、增廣路

17、徑； c、割。這些是最大流最小割定理的精髓。（ Ford-Fulkerson 方法沿增廣路徑反復(fù)增加流，知道找出最大流為止；而最大流最小割定理告訴我們：一個(gè)流是最大流， 當(dāng)且僅當(dāng)它的殘留網(wǎng)絡(luò)不包含增廣路徑。）一、殘留網(wǎng)絡(luò)：在不超過容量c（ u ，v）的條件下，從u到v之間可以壓入的額外網(wǎng)絡(luò)流量，就是（ u， v）殘留容量，定義為 cf（ u， v） =c （ u， v） -f （ u ， v）。注意課本 401 頁的殘留網(wǎng)絡(luò)的例子。殘留網(wǎng)絡(luò) Gf本身也是一個(gè)流網(wǎng)絡(luò)，其容量由 cf給出，且 |Ef |<=2|E| 。注意課本 402頁的引理 26.2。二、增廣路徑：注意課本403頁引理 2

18、6.3 和引理 26.4 。三、流網(wǎng)絡(luò)的割：注意403頁的幾個(gè)引理。四、最大流最小割定理：幾個(gè)相互等價(jià)的條件。FORD-FULKERSON(G, s, t)1 foreach edge (u, v) EG2do fu, v 03fv, u 04 whilethere exists a path p from s to t in the residual network G5do cf(p) min cf(u, v) : (u, v) is in p6for each edge (u, v) in p7do fu, v fu, v + cf(p)fWord 資料.8fv, u -fu, vFOR

19、D-FULKERSON的復(fù)雜性： FORD-FULKERSON過程的運(yùn)行時(shí)間取決于如何決定第四行中的增廣路徑，選擇不好，算法可能不會(huì)終止。假設(shè)容量是整數(shù)? 13 行O(|E|)? 48 循環(huán)執(zhí)行 O(|f*|)? 找增廣路 O(|E|)? O(|E|f*|)FORD-FULKERSON算法有其缺點(diǎn)，可以參照課本406頁。4）Edmonds-Karp 算法：如果在第四行中用廣度優(yōu)先搜索來實(shí)現(xiàn)對(duì)增光路徑p的計(jì)算。 即如果增光路徑是殘留網(wǎng)絡(luò)中從s到 t 的最短路徑（其中每條邊為單位距離，或權(quán)），則能夠改進(jìn)FORD-FULKERSON算法的界；稱FORD-FULKERSON方法的這種實(shí)現(xiàn)為Edmond

20、s-Karp算法。Edmonds-Karp 算法的運(yùn)行時(shí)間為O（ V*E2）注意課本 407 頁關(guān)于 Edmonds-Karp 算法的一些證明。8、 NP 完全問題（多項(xiàng)式時(shí)間規(guī)約）?？键c(diǎn)：多項(xiàng)式時(shí)間的規(guī)約問題，掌握NP 完全問題的證明方法。P類問題：是在多項(xiàng)式時(shí)間可解的問題，即都是在O（ nk）時(shí)間求解的問題，此處k為某個(gè)常數(shù)，n是問題的輸入規(guī)模。NP類問題：是在多項(xiàng)式時(shí)間“可驗(yàn)證”的問題即能夠在問題輸入規(guī)模的多項(xiàng)式時(shí)間，驗(yàn)證該問題是正確的。注意： P問題包含于 NP 問題。但 P不一定是 NP問題的真子集。NPC問題： NP完全問題，即任何一個(gè)NP問題都能通過一個(gè)多項(xiàng)式時(shí)間算法轉(zhuǎn)換為某個(gè)N

21、P 問題，那么這個(gè) NP問題就成為 NPC問題。換言之，如果這個(gè)問題解決了，那么所有的NP問題也都能解決了。 若問題 L滿足L NP, andLP L for every LNP.則問題 L是 NPC的，若 L只滿足條件 2則稱問題是 NP-hard 的。注意：如果任何 NP完全問題可以在多項(xiàng)式時(shí)間解決，則 NP中所有問題都有一個(gè)多項(xiàng)式時(shí)間的算法。1）多項(xiàng)式時(shí)間的規(guī)約：若問題 2可以被多項(xiàng)式時(shí)間求解，則問題1也可被多項(xiàng)式時(shí)間求解；若問題 1不能被多項(xiàng)式時(shí)間求解，則問題2也不能多項(xiàng)式時(shí)間求解； problem1 p problem2 表明：問題 1的求解不 “ 難 ”于問題 2。假定一個(gè)判定問題

22、A和另外一個(gè)不同的判定問題B，在一個(gè)過程中，它能將A的任何勢(shì)力 a轉(zhuǎn)換為B的、具有以下特征的勢(shì)力b：a、轉(zhuǎn)化操作需要多項(xiàng)式時(shí)間；b、兩個(gè)實(shí)例的答案是相同的，即a的答案是“是”，當(dāng)且僅當(dāng)b的答案也是“是”，稱這樣的過程為多項(xiàng)式時(shí)間的規(guī)約算法?？梢詤⒄照n本599 頁的圖。a、給定問題 A的一個(gè)實(shí)例 a，利用多項(xiàng)式時(shí)間規(guī)約算法，將它轉(zhuǎn)換為問題B的一個(gè)實(shí)例 b 。b、在實(shí)例 b上，運(yùn)行 B的多項(xiàng)式時(shí)間判定算法。c、將 b 的答案用作 a的答案?？梢詫?duì)問題 A的求解“規(guī)約”為對(duì)問題B的求解。Word 資料.注意：第一個(gè) NP完全問題就是電路可滿足性問題。2） NP完全性與可歸約性：課本 609頁引理

23、34.33）電路可滿足性問題：引理：電路可滿足性問題屬于NP類、 NP難度及 NP完全的。例題解析：1 、設(shè)有一個(gè)長度為 N 的數(shù)字串，要求選手使用 K個(gè)乘號(hào)將它分成 K+1 個(gè)部分，找出一種分法，使得這 K+1 個(gè)部分的乘積能夠?yàn)樽畲蟆?（ EX：有一個(gè)數(shù)字串： 312 ，當(dāng) N=3 ， K=1 時(shí)會(huì)有以下兩種分法： 3*12=36 、 31*2=62 ，這時(shí)，符合題目要求的結(jié)果是：31*2=62 。）2、Olay 教授是一家石油公司的顧問，這家公司正在計(jì)劃建造一條由東向西的大型管道，它穿過一個(gè)有 n口油井的油田。從每口井中都有一條噴油管道沿最短路徑與主管道直接連接（或南或北）。給定各口井的

24、 x坐標(biāo)和 y坐標(biāo)，應(yīng)如何選擇主管道的最優(yōu)位置 （使得各噴管長度總和最?。?？證明最優(yōu)位置可在線性時(shí)間確定。3、 NPC證明：如集合的等劃分問題，TSP問題，最小頂點(diǎn)覆蓋問題。一、證明：頂點(diǎn)覆蓋問題是NP 完全問題。將 3SAT變換到 VC. 設(shè)U=u1,u2,.,un,C=c1,c2,.,cm 是 3SAT的實(shí)例 . 如下構(gòu)造圖 G, 分量設(shè)計(jì)法 .真值安排分量:Ti=(Vi,Ei), 1 i n, 其中 Vi=ui, i, Ei=ui, i任意覆蓋必至少包含ui或i中的一個(gè) ,否則不能覆蓋邊ui 或i.滿足性檢驗(yàn)分量:Sj=(Vj ,Ej ), 1jm,其中Vj =a1j,a2j,a3jE

25、j =a1j,a2j,a1j,a3j,a2j,a3j覆蓋至少包含 Vj 中的兩個(gè)頂點(diǎn) ,否則不能覆蓋 Ej 中的三角形聯(lián)絡(luò)邊 :溝通分量之間的關(guān)系對(duì)于每個(gè)子句cj, 設(shè)cj = xj,yj,zj,則Ej =a1j,xj,a2j,yj,a3j,zjG = (V,E)V = (V1V2. Vn)(V1V2. Vm )E = E1E2.En)(E1E2. Em)(E1E2.Em )K = n +2m顯然構(gòu)造可在多項(xiàng)式時(shí)間完成例如U = u1,u2,u3,u4,C = u1, 3,4,1,u2,4,則G如下， K=4+2 ×2=8Word 資料.設(shè) V 是 V 中不超過 K的頂點(diǎn)覆蓋 , 則

26、 V 中必包含 Ti中的一個(gè)頂點(diǎn)和每個(gè) Ej 中的兩個(gè)頂點(diǎn) , 至少要 n+2m 個(gè)頂點(diǎn) . 而 K=n+2m, 故 V 中一定只包含每個(gè) Ti中的一個(gè)頂點(diǎn)和每個(gè) Ej 中的兩個(gè)頂點(diǎn).如下得到賦值uiVt(ui)=Ti Vt(ui)=FEj 中的三條邊有兩條被VjV 中的頂點(diǎn)覆蓋, 第三條必被 VVi中的頂點(diǎn)覆蓋. 這表示在 Vi中的這個(gè)頂點(diǎn)對(duì)應(yīng)的文字取真. 所以子句 cj被滿足 . 從而 C被滿足 .設(shè) t: UT,F是滿足 C的一組賦值 . 若 t(ui)=T,則在 Ti中取頂點(diǎn) ui, 否則取i. 因?yàn)?t滿足子句 cj,在 Ej 中的三條聯(lián)絡(luò)邊中至少有一條被覆蓋, 那么取 Ej 中的另

27、兩條邊的端點(diǎn)作為V 中的端點(diǎn)即可 .二、證明： TSP（旅行商問題）問題是NP完全問題。首先來說明 TSP問題屬于 NP。給定該問題的一個(gè)實(shí)例，用回路中 n個(gè)頂點(diǎn)組成的序列作為證書。驗(yàn)證算法檢查該序列是否恰好包含每個(gè)頂點(diǎn)一次，并且對(duì)邊的費(fèi)用求和后，檢查和是否至多為 k。為了證明 TSP是 NP難度的，先證明 HAM-CYCLE<= PTSP。設(shè) G= （V，E）是 HAM-CYCLE 額一個(gè)實(shí)例。構(gòu)造 TSP的實(shí)力如下，建立一個(gè)完全圖 G= （ V， E ），其中 E = （ i， j）： i， j 屬于 V 且i ！ =j ，定義費(fèi)用函數(shù)為c（ i， j） =0 ，如果（ i， j）屬

28、于 E1，如果（ i， j）不屬于 ENotice ：因?yàn)?G是無向圖，它沒有自環(huán)路，因而對(duì)所有的頂點(diǎn)v屬于 V，都有 c（v， v） =1 ，于是<G ，c， 0> 就是 TSP的一個(gè)實(shí)例，它很容易在多項(xiàng)式時(shí)間產(chǎn)生?，F(xiàn)在說明圖 G中具有一個(gè)漢密爾頓回路，當(dāng)且僅當(dāng)圖G 中有一個(gè)費(fèi)用至多為 0的回路。假定圖 G中有一個(gè)漢密爾頓回路h， h中的每條邊度屬于E，因此在 G 中的費(fèi)用為 0。因此 h在 G中的費(fèi)用為0的回路。反之，假定圖G 中有一個(gè)費(fèi)用 h 至多為0的回路。由于 E 中邊的費(fèi)用只能是 0或 1，故回路 h的費(fèi)用就是0，且回路上每條邊的費(fèi)用必為0。故 h僅包含E中的邊。三、證明：集合的等劃分問題是NP完全問題。實(shí)例：有窮集 A， a A, s(a) Z+.問：是否存在 A A，使得s( a)s(a)顯然均分是aA 'a A A'NP 類問題。下面將3DM 變換到均分問題設(shè)W,X,Y,MW X Y 是3DM 的實(shí)例，其中 |W| = |X| = |Y| = q ，W = w1,w2,wqX = x1,x2, ,xqY = y1,y2,yqM = m1,m2,mkWord 資料.構(gòu)造 A， |A| = k +2對(duì)應(yīng)于每個(gè) mi = (wf(i),xg(i),yh(i)有 ai.s(ai)為二進(jìn)制數(shù)，分成3q 段，每段有 p =l