完全理論與近似算法

《完全理論與近似算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第15講NP完全性理論與近似算法1學(xué)習(xí)要點理解RAM，RASP和圖靈機計算模型理解非確定性圖靈機的概念理解P類與NP類語言的概念理解NP完全問題的概念理解近似算法的性能比及多項式時間近似格式的概念通過范例學(xué)習(xí)NP完全問題的近似算法（1）頂點覆蓋問題；（2）旅行售貨員問題；（3）集合覆蓋問題；（4）子集和問題。215.1計算模型在進行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型，包括定義該計算模型中所用的基本運算。建立計算模型的目的是為了使問題的計算復(fù)雜性分析有一個共同的客觀尺度。3個基本計算模型：隨機存取

2、機RAM(RandomAccessMachine)；隨機存取存儲程序機RASP(RandomAccessStoredProgramMachine)圖靈機(TuringMachine)。這3個計算模型在計算能力上是等價的，但在計算速度上是不同的。315.1.1隨機存取機RAM1、RAM的結(jié)構(gòu)415.1.1隨機存取機RAM2、RAM程序一個RAM程序定義了從輸入帶到輸出帶的一個映射?？梢詫@種映射關(guān)系作2種不同的解釋。解釋一：把RAM程序看成是計算一個函數(shù)若一個RAM程序P總是從輸入帶前n個方格中讀入n個整數(shù)x1，x2，…，

3、xn，并且在輸出帶的第一個方格上輸出一個整數(shù)y后停機，那么就說程序P計算了函數(shù)f(x1，x2，…，xn)=y解釋二：把RAM程序當(dāng)作一個語言接受器。將字符串S=a1a2…an放在輸入帶上。在輸入帶的第一個方格中放入符號a1，第二個方格中放入符號a2，…，第n個方格中放入符號an。然后在第n+1個方格中放入0，作為輸入串的結(jié)束標(biāo)志符。如果一個RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出帶的第一格輸出一個1并停機，就說程序P接受字符串S。515.1.1隨機存取機RAM3、RAM程序的耗費標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費標(biāo)準(zhǔn)在均勻耗費

4、標(biāo)準(zhǔn)下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間。以后除特別注明，RAM程序的復(fù)雜性將按照均勻耗費標(biāo)準(zhǔn)衡量。標(biāo)準(zhǔn)二：對數(shù)耗費標(biāo)準(zhǔn)對數(shù)耗費標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費與以二進制表示的指令的操作數(shù)長度成比例。在RAM計算模型下，假定一個寄存器可存放一個任意大小的整數(shù)。因此若設(shè)l(i)是整數(shù)i所占的二進制位數(shù)，則615.1.2隨機存取存儲程序機RASP1、RASP的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據(jù)2個連續(xù)的寄存器。第一個寄存器存

5、放操作碼的編碼，第二個寄存器存放地址。RASP指令用整數(shù)進行編碼。2、RASP程序的復(fù)雜性不管是在均勻耗費標(biāo)準(zhǔn)下，還是在對數(shù)耗費標(biāo)準(zhǔn)下，RAM程序和RASP程序的復(fù)雜性只差一個常數(shù)因子。在一個計算模型下T(n)時間內(nèi)完成的輸入-輸出映射可在另一個計算模型下模擬，并在kT(n)時間內(nèi)完成。其中k是一個常數(shù)因子?？臻g復(fù)雜性的情況也是類似的。715.1.3圖靈機815.1.3圖靈機根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現(xiàn)下面3個操作之一或全部。(1)改變有限狀態(tài)控制器中的狀態(tài)。(2)清除當(dāng)

6、前讀寫頭下的方格中原有帶符號并寫上新的帶符號。(3)獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當(dāng)前單元不動(S)。k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限個狀態(tài)的集合。(2)T是有限個帶符號的集合。(3)I是輸入符號的集合，I?T。(4)b是唯一的空白符，b∈T-I。(5)q0是初始狀態(tài)。(6)qf是終止(或接受)狀態(tài)。(7)δ是移動函數(shù)。它是從Q?Tk的某一子集映射到Q?(T?{L，R，S})k的函數(shù)。915.1.3圖靈機圖靈機

7、M的時間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數(shù)。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。圖靈機的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。與RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數(shù)的裝置。1015.2P類與NP類問題一般地說，將可由多項式時間算法求解的問題看作是易處理的問題，而將需要超多項式時間才能求解的問題看作是難處理的問題。有許多問題，從表面上看似乎并不比排序

8、或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項式時間算法，也沒有人能夠證明這些問題需要超多項式時間下界。在圖靈機計算模型下，這類問題的計算復(fù)雜性至今未知。為了研究這類問題的計算復(fù)雜性，人們提出了另一個能力更強的計算模型，即非確定性圖靈機計算模型，簡記為NDTM(NondeterministicTur