算法導(dǎo)論復(fù)習(xí)資料-資料下載頁
2025-08-05 10:50本頁面
【正文】 的一個頂點(diǎn)和每個Ej’中的兩個頂點(diǎn). 如下得到賦值 ui206。V’ 219。 t(ui)=T ūi206。V’ 219。 t(ui)=F Ej’’中的三條邊有兩條被Vj’199。V’中的頂點(diǎn)覆蓋, 第三條必被V’199。Vi中的頂點(diǎn)覆蓋. 這表示在Vi中的這個頂點(diǎn)對應(yīng)的文字取真. 所以子句cj被滿足. 從而C被滿足. 設(shè)t: U174。{T,F}是滿足C的一組賦值. 若t(ui)=T, 則在Ti中取頂點(diǎn)ui, 否則取ūi. 因為t滿足子句cj, 在Ej’’中的三條聯(lián)絡(luò)邊中至少有一條被覆蓋, 那么取Ej’’中的另兩條邊的端點(diǎn)作為V’中的端點(diǎn)即可. 二、證明：TSP（旅行商問題）問題是NP完全問題。 首先來說明TSP問題屬于NP。給定該問題的一個實(shí)例，用回路中n個頂點(diǎn)組成的序列作為證書。驗證算法檢查該序列是否恰好包含每個頂點(diǎn)一次，并且對邊的費(fèi)用求和后，檢查和是否至多為k。 為了證明TSP是NP難度的，先證明HAMCYCLE=PTSP。設(shè)G=（V，E）是HAMCYCLE額一個實(shí)例。構(gòu)造TSP的實(shí)力如下，建立一個完全圖G’=（V，E’），其中E’={（i，j）：i，j屬于V且i！=j}，定義費(fèi)用函數(shù)為c（i，j）={0，如果（i，j）屬于E {1，如果（i，j）不屬于ENotice：因為G是無向圖，它沒有自環(huán)路，因而對所有的頂點(diǎn)v屬于V，都有c（v，v）=1，于是G’，c，0就是TSP的一個實(shí)例，它很容易在多項式時間內(nèi)產(chǎn)生。 現(xiàn)在說明圖G中具有一個漢密爾頓回路，當(dāng)且僅當(dāng)圖G’中有一個費(fèi)用至多為0的回路。假定圖G中有一個漢密爾頓回路h，h中的每條邊度屬于E，因此在G’中的費(fèi)用為0。因此h在G’中的費(fèi)用為0的回路。反之，假定圖G’中有一個費(fèi)用h‘至多為0的回路。由于E’中邊的費(fèi)用只能是0或1，故回路h’的費(fèi)用就是0，且回路上每條邊的費(fèi)用必為0。故h‘僅包含E中的邊。 三、證明：集合的等劃分問題是NP完全問題。 實(shí)例：有窮集A，a206。A, s(a)206。Z+. 問：是否存在A’205。A，使得顯然均分是NP類問題。下面將3DM變換到均分問題 設(shè)W,X,Y,M 205。 W180。X180。Y 是3DM的實(shí)例，其中|W| = |X| = |Y| = q， W = {w1,w2,… ,wq} X = {x1,x2,… ,xq} Y = {y1,y2,… ,yq} M = {m1,m2,… ,mk}構(gòu)造A，|A| = k +2對應(yīng)于每個mi = (wf(i),xg(i),yh(i)) 有ai.s(ai)為二進(jìn)制數(shù)，分成3q段，每段有p = 233。log(k+1)249。位,共計3pq位，每段對應(yīng)一個W200。X200。Y中的元素. Wf(i),xg(i),yh(i) 所代表的段的最右位為1，其它為0. w1w2…wqx1x2…xqy1y2…yq注：p179。log(k+1)，2p 179。k+1，k163。 2p1 , 當(dāng) k個1相加時不會產(chǎn)生段之間的進(jìn)位令B的段數(shù)與s(ai)一樣，每段的最右位為1，其它為0例如：W={w1,w2},X={x1,x2},Y={y1,y2}, M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)}p=233。log(3+1)249。=2元素a1,a2,a3分別對應(yīng) (w1,x2,y2),(w1,x2,y1),(w2,x1,y1) s(a1) = 01 00 00 01 00 01 = 210 + 24 + 20 s(a2) = 01 00 00 01 01 00 = 210 + 24 + 22 s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22 B = 01 01 01 01 01 01 子集A’ = {ai:1163。i163。k} 滿足 當(dāng)且僅當(dāng) M’ = {mi: ai206。A’}是M的匹配 A的最后兩個元素b1,b2 考慮包含b1的子集A’, 必有因此A’{b1}的元素對應(yīng)的三元組構(gòu)成M的匹配反之，若子集M’構(gòu)成M的匹配，則 A’ = {b1}200。{ai: mi206。M’}滿足證明題的考點(diǎn)：正確性證明問題。替換法證明問題。貪心選擇性質(zhì)證明問題。NP完全問題的證明。最大流問題的證明。簡單題的考點(diǎn)：回溯法基本思想和步驟。分治算法的基本方法和步驟。搜索算法的基本方法和步驟。動態(tài)規(guī)劃問題的基本方法和步驟。分支界限算法的基本方法和步驟。第 13 頁 共 13 頁
電大資料相關(guān)推薦
鄂ICP備17016276號-1