算法分析與設(shè)計ss lecture7

Turing機的定義雙向無限帶的Turing基本模M=<,,qTuring機的定義雙向無限帶的Turing基本模M=<,,q0B,F其中QB有窮狀態(tài)有窮帶字符集輸入字符集空白字符,q0初始狀態(tài)qY,FF終結(jié)狀態(tài)集Q×狀態(tài)轉(zhuǎn)移函:帶B讀寫…B有限狀態(tài)控制2瞬時描述-格局(ID)1q瞬時描述-格局(ID)1q2表示此刻Turing機的FSC處于狀態(tài)q讀寫頭指在串2的第一個字符.例如TuringM的某時刻的狀態(tài)轉(zhuǎn)移函數(shù)(q,xi)=帶上的字x1x2xixn讀寫頭指向xi則它的瞬間描述是x1x2...xi-1qxi...xnx1x2...xi-2pxi-1Yxi+1...表示由左邊的ID一步達到右邊的表示由左邊的ID經(jīng)有限步達到右邊的3實L0n1n實L0n1n|n1設(shè)計接LTuring機如下M=,,,q0,Q={q0,q1,q2,q3,qY,qN={0,={0,1,X,Y,BF={qY初始將字符串放1n方格中,FSC處在狀態(tài)q0,讀寫指向方1.將第一個0改寫X,然后帶頭向右掃描.遇到一個1將1改為Y然后帶頭向左掃描遇到第一X改為向右掃描這時進入下一個巡回.每個巡回01改為Y直到接受或拒斥停機4實例（續(xù)轉(zhuǎn)移函數(shù)如例如輸機動作如下q00011 Xq10110Y1實例（續(xù)轉(zhuǎn)移函數(shù)如例如輸機動作如下q00011 Xq10110Y11Y1 Y112YYXXq0YYXXYYq3501XYBTuring機接受語言被Turing機接受語言被M接受的語言記作L(M)，是*上的字的集合當這些字左端對齊1放在帶上M處于q0M的帶頭指向1時經(jīng)過有限步M將停機在接受qY即L(M)={|*,1,2*(q0*1qY2)}如果字不是L(M)中的字, M可以不停機或停機在拒斥狀態(tài)Turing機可以推廣k條帶Turing確定型Turing機可以推廣到非確定Turing6基本Turing機的變種單向無限帶Turing帶方格從1開始基本Turing機的變種單向無限帶Turing帶方格從1開始向右無限長其它與基Turing機相同多帶Turingk條雙向帶k個讀寫頭k為大1的常數(shù).初始將輸入寫在第一條帶的1n內(nèi).其它帶為空.每個讀寫頭掃描一條帶,可以改寫被掃描方格的字符,讀寫頭然后向左或向右移動一個方格.讀寫頭FSC的狀態(tài)及k條帶所掃描的k個字符來決定7實例例LwcwR實例例LwcwR|w為0-1字符串設(shè)計L的TuringM2M1的時間復雜度為O(nM2的空間復雜度為O(logn).當發(fā)c時第M1有2條帶,c左邊的w復制到第2條帶上2條帶的讀寫頭向左,輸入帶的讀寫頭向右.比較兩個帶頭的符號,如果符號一樣,字符個數(shù)一樣,M1x.M1至多作n+1個動作時間復雜度n+1.空間復雜(n-1)/2+1.M2有2條帶第2條帶作為二進制的計數(shù)器首先檢查輸入是否只有1cc左邊和右邊的符號是否一樣多然后逐個比較c左邊和右邊的字符,用上述計數(shù)器找到對應(yīng)的字符.如果所有的字符都一樣M2接受停機空間復雜度為二進制的計數(shù)器的占用空間,O(logn).時間復雜O(n2).8計算復計算復雜性理論空間和時間復雜度的形式定義確定型Turing計算復雜度的有關(guān)結(jié)果帶壓縮線性加速帶數(shù)目的減9確定型Turing空間復雜度的確定型Turing空間復雜度的形式定義&$離線的Turing1條具有端記號的只讀輸入帶k半無限存儲帶.如果對每個長為n的輸入串,M在任一存儲帶上都至多S(n)那么M在最壞情況下的空間復雜度為S(n).確定型Turing機時復雜度的形式確定型Turing機時復雜度的形式定義k條雙向帶Turing一條帶包含輸入如果對于每個長為n的輸入串M在停機前至多做個動作那么稱M在最壞情況下的時間復雜度為兩條假設(shè)：空間復雜性至少需要時間復雜性至少需要讀入輸入的時因此這里作如下規(guī)定對一切nS(n)1lognmax{1,logn}的縮寫對一切nT(n)n+1,T(n)max{n+1,T(n)}的縮寫有關(guān)計算復雜度的結(jié)果帶M2模擬M1的復雜類帶壓有關(guān)計算復雜度的結(jié)果帶M2模擬M1的復雜類帶壓cS(n),0<cT(n)liminfT(n) n 時間加cT(n),帶數(shù)目減少空間不變帶數(shù)目減少時間增加7.1P類與NP易解的問題與難解的問題排序O(nlog7.1P類與NP易解的問題與難解的問題排序O(nlogn)Dijkstra算法O(n2)，最大團回溯法用一臺每秒10次的超大型計算機，上述算法的時間105log21051.7106，t=1.710-310萬個數(shù)據(jù)排序1萬個頂點的圖的單源最短路徑(104)2=108,t=0.1100個頂點的圖的最大團,t=1.81032/109=1.81021秒=5.71015年,即5千7百萬億年1分鐘能解多大的問題.161010次運算可給2109=20億個數(shù)據(jù)排序用Dijkstra算法可解2.4105個頂點的圖的單源最短路徑問題回溯法1天只能解41個頂點的圖的最大團問題算法的時間復雜度f算法的時間復雜度fg是多項式相關(guān)的如果存在多pq使得對任意nN,f(n)p(q(n))g(n)q(f(n)).例如nlognn2,n2+2n+5n10都是多項式相關(guān)的,lognn,n52n不是多項式相關(guān)的.問題的實例I的規(guī)模:I的二進制編碼的長度記作定義7.1 如果存在函數(shù)f:NN使得對任意的規(guī)模為n的實例I,算法A對I的運算在f(n)步內(nèi)停止,則稱算法A的時復雜度多項式時間算法:以多項式為時間復雜度易解的問題:有多項式時間算法難解的問題不存在多項式時間算法幾點說1當采用合理的編幾點說1當采用合理的編碼時輸入的規(guī)模都是多項式相關(guān)的.“合理的”是指在編碼中不故意使用許多冗余的字符例如設(shè)實I是一個無向簡GV,EV={a,b,c,d},E={(a,b),(a,d),(b,c),(b,d),(c,d)用鄰接矩陣表示e1=0101/1011/0101/1110用關(guān)聯(lián)矩陣表示,編碼e2=11000/10110/00101/01011/,長G有n個頂點m條邊用鄰接矩陣時|I|=n(n+1),用關(guān)聯(lián)矩陣時|I兩者多項式相關(guān)自然數(shù)應(yīng)采用 (k2)進制編碼不能采用一進制編碼n的二進制編碼有l(wèi)og2(n+1)位一進制編碼有n位兩者不是多項式相關(guān)的.幾點說明時間復雜度常表成幾點說明時間復雜度常表成計算對象的某些自然參數(shù)的函數(shù)，如圖的頂點數(shù)或邊數(shù)的函數(shù).實例的二進制編碼的長度與這自然參數(shù)通常是多項式相關(guān)的運行時間通常是計算執(zhí)行的操作指令數(shù)，執(zhí)行的指令數(shù)與實際運行時間是多項式相關(guān)的要求每一條指令的執(zhí)行時間是固定的常數(shù)規(guī)定一個基本操作指令集，可由位邏輯運算與、或、非組成，任何可用這個基本操作指令集中常數(shù)條指令實現(xiàn)的操作都是合理的指令，由有限種合理的指令構(gòu)成的操作指令集是合理的操作指令集.在上述約定下作指令集無關(guān)，算法是否是多項式時間的與采用的編碼和操從而一個問題是易解的、還是難解的也與采用的編碼和操作指令集無關(guān)易解的問題與難解的問題易解的問易解的問題與難解的問題易解的問題如排序、最小生成樹、單源最短路徑已證明的難解問題(1)不可計算的即根本不存在求解的算法如希爾伯特第十問題丟番圖方程(有一個或幾個變量的整系數(shù)方程)是否有整數(shù)解有算法但至少需要指數(shù)或更多的時間或空間，如帶運算的正則表達式的全體性即任給字母表A上的帶冪運問:R=A*?這個問題至少需要指數(shù)空間的正則表達式既沒有找到多項式時間算法、又沒能證明是難解的問題如哈密頓回路問題、貨郎問題、背包問題7.1.2判定問題判定問題:答案只有兩個是否7.1.2判定問題判定問題:答案只有兩個是否<D,Y其中D是實例集合YD是所判定問答案為Yes的實例哈密頓回路任給無向圖問G有哈密頓回路嗎貨郎(TSP):n個城市城市i與城j之間的正整數(shù)距離d(i,j),ij1ijn以及正整D問有一條每一個D市恰好經(jīng)過一次最后回到出發(fā)點且長度不超的巡回路嗎即12n的排使得d((i),(i1))d((n),(1))Di0-1背包的判定問題與優(yōu)化問0-1背包的判定問題與優(yōu)化問0-1背包n件物品和一個背包i的重wi,價vi1in,以及背包的重量B和價值目K,其wiviB,K均為正整數(shù)問能在背包中裝入總價值不少于KB的物品嗎即存在子集T{1,2使K且搜索問題、組合優(yōu)化問題與判定問題的對應(yīng)如果搜索問題、組合優(yōu)化問題有多項式時間算法,則對應(yīng)的判定問題也有多項式時間算法;通常反之亦真組合優(yōu)化問題與判定問題*由組合優(yōu)化問題與判定問題*由3部分組成組合優(yōu)化問題(1)實例集DID*有一個有窮非空集S(I其元素稱作I的可行解sS(I),有一個正整數(shù)c(s),稱作s的值s*S(I),對所sS(I),當*是最()化問題時c(s*)(c(s*)c(s)s*I的最優(yōu)解c(s*)I的最優(yōu)值記作*對應(yīng)的判定問題D,Y>定義如下DI,K|ID*KZ*其中Z*是非負整數(shù)集合.當*是最小化問題時Y={(I,K)|OPT(I)K};當*是最大化問題時Y={(IK)|OPT(I)K(nondeterministic所有多項式時間可解的判定(nondeterministic所有多項式時間可解的判定問題組成的問題類定義P類設(shè)判定問題定義=<D,Y>,如果存在兩個輸入變量p，對每一個實例ID,IY多項式時間算A和多項式t,|t|p(|I|A對輸It輸出“Yes”且僅當存在稱 是多項式時間可驗證的,A是IY時,tIY的證據(jù)的多項式時間驗證算法由所有多項式時間可驗證的判定問題組成的問題類稱類TSP(貨郎),0-1背包HC(哈密頓回路非確定型多項式時間算法非確定型多項式時間算法非確定型多項式時間算(1對給定的實I首先“猜想”一t|t|p(|It是否是證IY的證(2)然后檢猜想和檢查可以在多項式時間內(nèi)完當且僅當IY時能夠正確地猜想到一個證據(jù)*注：非確定型多項式時間算法不是真正的算定理 t問題多項式時間變換與NP完全性多項式時多項式時間變換與NP完全性多項式時間變換如何比較兩個問題的難度定義 設(shè)判定問題1=<D1,Y1>,2=f:D1D2滿足條件如果函(1)是多項式時間可計算的(2)對所ID1IY1則稱f是1到2的多項式時間變換如果存12的多項式時間變換則稱可多項式1間變換2,記作1p例例 HC例例 HC的每一個IG=<V,E>,TSP對應(yīng)的f(I為V,任意兩個不同的城市的距離uv之間若(u,v否則d(u,v)以及D|V例任給連通的無向賦權(quán)圖最小生成樹例任給連通的無向賦權(quán)圖最小生成樹以及正整B,其中權(quán)W:EZ+,問有權(quán)不超過B的生成樹嗎最大生成樹任給連通的無向賦權(quán)圖以及正整D,其中權(quán)W:EZ+,問G有權(quán)不小于D的生成樹嗎例 最大生成樹p最小生成樹證任給最大生成樹的實例I:連通的無向賦權(quán)圖和正整數(shù)D最小生成樹的對應(yīng)f(I圖G=<V,E,W>和正整B=(n1)MD,其中 M=max{W(e)|eE W(e)=MW(e)如果存在G的生成樹T,使W(e)(n1)MW(e)(n1)MDe反之亦然e多項式時間可計算f變換實例262633554474145317最小生變換實例262633554474145317最小生成樹T’的實例G’W(T')32最大生成樹的實GM8，W(T)16W'(e)(n1)MWeTp的性定理7.2pp的性定理7.2p具有傳遞性.即,設(shè)1p2,2p3,則1p3.i=<Di,Yii=1,2,3,fg1223的多項式時間變換.對每一個ID1,令h(I)=g(f(I)).fg的時間上界分別為pq不妨pq是單調(diào)遞增的.h的步數(shù)不p(|I|輸?shù)某鲎鳛楹侠淼闹噶钜徊街荒茌敵鲩L度不超過固定值字符串,|f(I)|kp(|I|于是p(|I|)+q(|f(I)|)p(|I|)+q(kp(|I得證h是多項式時間可計算的對每一個IY1f(I)Y2h(I)得證h3的多項式時間變換1p的性1p2p的性1p2,2P蘊涵1P.定理1=<D1,Y12=<D2,Y2>,f12的多項式時間變換A是計f的多項式時間算法B2的多項式時間算法.如下構(gòu)造1的算C:對每一ID1,應(yīng)用A得到f(I(3)C輸出Yes當且僅B輸出設(shè)1p2,則1是難解的蘊2是難解的推論由例7.2及最小生成樹P,得知最大生成樹P.由例7.1HCP.反過來HC是難解的TSP也是難解的7.2.2NP完全性如果對所有NP,p7.2.2NP完全性如果對所有NP,p則稱定義7.5定理7.4推論定理7.5NP難的.推論7.3, 則是NP難的NP難的NP,NP完全的P,如果存在NP難的問題假設(shè)PNP,那么,如果是NP難的,p,如果存在NP難的問題是如果NP并且存在是NP完全的.NP完全問題p證明NP完全性的捷徑證明NP;找到一個已知的NP完全問題,并證明p.Cook-Levin定理合式公Cook-Levin定理合式公式：由變元、邏輯運算符以及圓括號按照一定的規(guī)組成的表達式變元和它的否定稱作文字有限個文字的析取稱作簡單析取式有限個簡單析取式的合取稱作合取范式給定每一個變元的真假值稱作一個賦值如果賦t使得合式公F為真,tF的成真賦值.如果F存在成真賦值,則稱F是可滿足的例如F1=(x1x2)(x1x2x3)x2是一個合取范式F1是可滿足的令t(x1)=1,t(x2)=0,t(x3)=1是F1的成真賦值F2=(x1x2x3)(x1x2x3x2x3不是可滿足的Cook-Levin定理可滿足(SAT):任給一個合取Cook-Levin定理可滿足(SAT):任給一個合取范F,F是可滿足的嗎定理(Cook-Levin定理是NP完全的證明思想：對于任意一個NP類中語言L，存在一個接受它非確定型圖靈機構(gòu)造L到SAT的多項式變換對于L中的任意串x，M對x的接受計算變換成一個SAT問題的肯定實定理7.7P=NP的充分必要條件是存在NP完全問題P.7.3幾個NP完全問題恰好覆最大可滿足子集7.3幾個NP完全問題恰好覆最大可滿足子集有向雙機調(diào)背獨立裝團最大可滿足性與三元可滿足性最大可最大可滿足性與三元可滿足性最大可滿足性(MAX-任給關(guān)于變元x1,xn的簡析取C1,C2,,Cm及正整K問存在x1x2,的賦值使得C1,C2,,Cm中至少有個為真嗎3元合取范式每一個簡單析取式恰好有3個文字的合取范式.三元可滿足性(3SAT):任給一個3元合取范式F,問F是可滿足的嗎?子問題：設(shè)判定問題=<D,Y>,=<D,Y>,如果DD,YDY,是的特殊情況,的子問題SAT是MAX-SAT的子問題(取定理7.8MAX-SAT是NP完全3SAT是SAT的子問題定理3SAT是NP完全的7.3.2頂點覆蓋、團與獨立集設(shè)無7.3.2頂點覆蓋、團與獨立集設(shè)無向圖G=<V,EVV.V是G的一個頂點覆蓋 G的每一條邊都至少有一個頂點在團對任u,vV且uv,都有(u,v)E.獨立集對任u,vV,都有(u,v)E.中引理7.1對任意的無向圖G=<V,E>和子集VV,下述命題是等價的:(1)是G的頂點覆蓋VV是G的獨立集VV是補Gc=<V,Ec>的團頂點覆蓋、團與獨立集任頂點覆蓋、團與獨立集任給一個無向圖G=<V,E>和非負整數(shù)頂點覆蓋問G有頂點數(shù)不超K的頂點覆蓋嗎團任給一個無向圖G=<V,E>和非負整數(shù)J|V|問G有頂點數(shù)不小于J的團嗎?獨立集任給一個G=<V,E>和非負J|V|問G頂點數(shù)不小于的獨立集嗎定理定理頂點覆蓋NP完全的獨立集和團是NP完全的4哈密頓回路、4哈密頓回路、貨郎問題與恰好覆蓋有向哈密頓回路:任給有向圖D,問:D中有哈密頓回路嗎?定理7.12有向HC是NP完全的.定理7.13HC是NP完全的定理7.14TSP是NP完全的恰好覆蓋給定有A={a1,a2,,an}和A的子集的集合{S1,S2,,Sm},問:存在子集UW使得U中子集彼此不交且它們的并集等于A? 稱U是A的恰好覆蓋.例如設(shè)A={1,2,3,4,5S1={1,2S2={1,3,4},S3={2,4},則{S2,S4}是A的恰好覆蓋定理恰好覆蓋是NP完全的子集和、背包、裝箱與雙機調(diào)子集和、背包、裝箱與雙機調(diào)度子集和:給定正整數(shù)集合X={x1,x2,,xn}及正整數(shù)N,問存X的子集T,使得T中的元素之和等于N嗎裝箱給定n件物品物品j的重量為正整數(shù)wj,1jn以及箱子數(shù)K.規(guī)定每只箱子裝入物品的總重量不超過正整數(shù)B,問能用K只箱子裝入所有的物品嗎?雙機調(diào)度有2臺機器n項作J1,J2,,Jn,這2臺機器完相同每一項作業(yè)可以在任一臺機器上進行沒有先后順序Ji的處理ti1in截止時間為ti在截止時都是正整數(shù),問能把n項作業(yè)分配給這2臺機器D內(nèi)完成所有的作業(yè)嗎NP完全性子集和是NPNP完全性子集和是NP完全的.0-1背包是NP完全的雙機調(diào)度是NP完全的裝箱是NP完全的定理定理7.17定理7.18定理注意0-1背包問題優(yōu)化形式的動態(tài)規(guī)劃算法其時間復雜為O(nB),其中n是物品的個數(shù),B是重量限制.這不是多項時間算法,而是指數(shù)時間算法偽多項式時間算法算法的時間|I|max(I的某個二元多p(|I|max(I))為上界,其中max(I)是實I中數(shù)的最大絕對值.NP完全性NP完全性理論的應(yīng)用用NP完全性理論進行子問題分析子問題的計算復雜性子問題的NP完全性證明NP難度搜索問Turing歸約NP-hard,NP-子問題的計算復子問題的計算復雜性?P努力擴大已知區(qū)域，縮小未知區(qū)當PNP時，存在不屬于NPC也不屬于P的問有先行約束多處理機有先行約束多處理機調(diào)度問題優(yōu)化問題給定任務(wù)Tm臺機器,tT,l(t)Z+,T上的偏序:T01D}滿足下述條件T為可行調(diào)度tT,(t)+l(t)i,0iD,|{tT:(t)i<(t)+l(t)}|(3)t,t?t’(t)+l(t)求使D最小的可行調(diào)度條件說明任務(wù)在截止時間前完成同時工作的臺數(shù)不m有偏序約束的任務(wù)必須按照約束先實112任務(wù)集如圖所D最小的可行調(diào)度求使得12實112任務(wù)集如圖所D最小的可行調(diào)度求使得121 判定問題實例：任務(wù)集T,m臺機器,tT,l(t)判定問題實例：任務(wù)集T,m臺機器,tT,l(t)Z+,T上的偏截止時問：是否存在小于等于的可行調(diào)度？子問題通過限制參數(shù)(機器數(shù)、工作時間、偏序)構(gòu)成參限偏樹任m大小m1,2,…,某個常數(shù)m任意l大小l為常l任意調(diào)度問題的子問題結(jié)構(gòu)從上到下：偏序任意、樹形偏序、無偏序約從調(diào)度問題的子問題結(jié)構(gòu)從上到下：偏序任意、樹形偏序、無偏序約從左到右：處理器臺數(shù)限制逐步放從前到后：各任務(wù)等長工作時間、任意工作時l任意任意為樹m任意搜索問題與優(yōu)化問題的難度Turing歸約搜索問題與優(yōu)化問題的難度Turing歸約設(shè)1,2是搜索問題，A是利用解2的假想子程序s解1算法，且只要s是多項式時間的，A也是多項式時間的，A是從1到2的多項式時間Turing歸約.這時也稱算法1Turing歸約NP難度2，記1∝T2.設(shè)是搜索問題，如果存在NP完全問題’使得’T稱是NP-hard.這意味著在多項式可計算的角度看，至少和NPC問題一樣難.許多NP完全問題對應(yīng)的優(yōu)化問題都是NP-hard實例—證明NP等價例貨郎問題（TSO實例—證明NP等價例貨郎問題（TSO）是NP等價的證：易證TSON