|
一、圖靈機
根據(jù)有限狀態(tài)控制器的當前狀態(tài)及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現(xiàn)下面3個操作之一或全部。
改變有限狀態(tài)控制器中的狀態(tài)。 清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。 獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當前單元不動(S)。
k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:
Q是有限個狀態(tài)的集合。 T是有限個帶符號的集合。 I是輸入符號的集合。 b是唯一的空白符，b∈T-I。 q0是初始狀態(tài)。 qf是終止(或接受)狀態(tài)。 δ是移動函數(shù)。
它是從Q×Tk的某一子集映射到Q×(T×{L，R，S})k的函數(shù)。
圖靈機M的時間復雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數(shù)。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。
圖靈機的空間復雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。
確定型圖靈機
有限狀態(tài)集Q，狀態(tài)q0:初始狀態(tài)；qy：接受狀態(tài)；狀態(tài)qn：不接受狀態(tài)。
字符集合{0, 1, b} ；其中b是空格符。
轉(zhuǎn)換功能：
輸入x = 101000b
執(zhí)行順序：
q0輸入1 （q0,r）右移磁頭到0 q0輸入0 （q0,r）右移磁頭到1 q0輸入0 （q0,r）右移磁頭到0 ... q0輸入b （q1,l）左移磁頭到0 q1輸入0 （q2,b） q2輸入b （q2,l）左移磁頭到0 q2輸入0 （q3,b） q3輸入b （qy，l）退出
二、P類與NP類問題
一般地說，將可由多項式時間算法求解的問題看作是易處理的問題，而將需要超多項式時間才能求解的問題看作是難處理的問題。
有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項式時間算法，也沒有人能夠證明這些問題需要超多項式時間下界。
在圖靈機計算模型下，這類問題的計算復雜性至今未知。
為了研究這類問題的計算復雜性，人們提出了另一個能力更強的計算模型，即非確定性圖靈機計算模型，簡記為NDTM(Nondeterministic Turing Machine)。
在非確定性圖靈機計算模型下，許多問題可以在多項式時間內(nèi)求解。
非確定性圖靈機
在圖靈機計算模型中，移動函數(shù)δ是單值的，即對于Q′Tk中的每一個值，當它屬于δ的定義域時，Q′(T′{L，R，S})k中只有唯一的值與之對應(yīng)，稱這種圖靈機為確定性圖靈機，簡記為DTM(Deterministic Turing Machine)。
非確定性圖靈機(NDTM）：一個k帶的非確定性圖靈機M是一個7元組：(Q，T，I，δ，b，q0，qf)。與確定性圖靈機不同的是非確定性圖靈機允許移動函數(shù)δ具有不確定性，即對于Q×Tk中的每一個值(q;x1,x2,…,xk)，當它屬于δ的定義域時，Q×(T×{L，R，S})k中有唯一的一個子集δ(q;x1,x2,…,xk)與之對應(yīng)。可以在δ(q;x1,x2,…,xk)中隨意選定一個值作為它的函數(shù)值。
P類與NP類語言定義
P={L|L是一個能在多項式時間內(nèi)被一臺DTM所接受的語言}
NP={L|L是一個能在多項式時間內(nèi)被一臺NDTM所接受的語言}
由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內(nèi)被確定性圖靈機接受的語言也可在多項式時間內(nèi)被非確定性圖靈機接受。故P í NP。
NP類語言舉例——無向圖的團問題
該問題的輸入是一個有n個頂點的無向圖G=(V，E)和一個整數(shù)k。要求判定圖G是否包含一個k頂點的完全子圖(團)，即判定是否存在V’ V，|V’|=k，且對于所有的u，v∈V’，有(u，v)∈E。
若用鄰接矩陣表示圖G，用二進制串表示整數(shù)k，則團問題的一個實例可以用長度為 的二進位串表示。因此，團問題可表示為語言：
CLIQUE={w#v|w，v∈{0，1}*，以w為鄰接矩陣的圖G有一個k頂點的團，其中v是k的二進制表示。}
接受該語言CLIQUE的非確定性算法：用非確定性選擇指令選出包含k個頂點的候選頂點子集V，然后確定性地檢查該子集是否是團問題的一個解。算法分為3個階段
算法的第一階段將輸入串w#v分解，并計算出n = ，以及用v表示的整數(shù)k。若輸入不具有形式w#v或|w|不是一個平方數(shù)就拒絕該輸入。顯而易見，第一階段可在 時間內(nèi)完成。
在算法的第二階段中，非確定性地選擇V的一個k元子集V’V。
算法的第三階段是確定性地檢查V’的團性質(zhì)。若V’是一個團則接受輸入，否則拒絕輸入。這顯然可以在 時間內(nèi)完成。因此，整個算法的時間復雜性為 。
非確定性算法在多項式時間內(nèi)接受語言CLIQUE，故CLIQUE∈NP.
NP完全問題
PNP。
直觀上看，P類問題是確定性計算模型下的易解問題類，而NP類問題是非確定性計算模型下的易驗證問題類。
大多數(shù)的計算機科學家認為NP類中包含了不屬于P類的語言，即P≠NP。
NP完全問題有一種令人驚奇的性質(zhì)，即如果一個NP完全問題能在多項式時間內(nèi)得到解決，那么NP中的每一個問題都可以在多項式時間內(nèi)求解，即P = NP。
目前還沒有一個NP完全問題有多項式時間算法。
三、NP完全問題的近似算法
迄今為止，所有的NP完全問題都還沒有多項式時間算法。
對于這類問題，通常可采取以下幾種解題策略。
只對問題的特殊實例求解 用動態(tài)規(guī)劃法或分支限界法求解 用概率算法求解 只求近似解 用啟發(fā)式方法求解
近似算法的性能
若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標函數(shù)值為c，則將該近似算法的性能比定義為 。
在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)ρ(n)，即。
該近似算法的相對誤差定義為：。若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間顯然有如下關(guān)系：。
旅行售貨員問題近似算法
問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。
旅行售貨員問題的一些特殊性質(zhì)： 比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。
對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。
void approxTSP (Graph g) { 選擇g的任一頂點r； 用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹T； 前序遍歷樹T得到的頂點表L； 將r加到表L的末尾，按表L中頂點次序組成回路H，作為計 算結(jié)果返回；
} 當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。
實現(xiàn)
/* 主題：近似算法——旅行售貨員問題 * 作者：chinazhangjie * 郵箱：chinajiezhang@gmail.com * 開發(fā)語言： C++ * 開發(fā)環(huán)境： Virsual Studio 2005 * 時間: 2010.12.06 */ #include #include #include using namespace std ; struct TreeNode { public: TreeNode (int nVertexIndexA = 0, int nVertexIndexB = 0, int nWeight = 0) : m_nVertexIndexA (nVertexIndexA), m_nVertexIndexB (nVertexIndexB), m_nWeight (nWeight) { } public: int m_nVertexIndexA ; int m_nVertexIndexB ; int m_nWeight ; } ; class MST_Prim { public: MST_Prim () {} MST_Prim (const vectorvectorint> >& vnGraph) { m_nvGraph = vnGraph ; m_nNodeCount = (int)m_nvGraph.size () ; } void SetData (const vectorvectorint> >& vnGraph) { m_nvGraph = vnGraph ; m_nNodeCount = (int)m_nvGraph.size () ; } // const vectorTreeNode>& GetMSTree () const { return m_tnMSTree ; } // const vectorvectorint> >& GetGraph () const { return m_nvGraph ; } void DoPrim () { // 是否被訪問標志 vectorbool> bFlag (m_nNodeCount, false) ; bFlag[0] = true ; int nMaxIndexA ; int nMaxIndexB ; int j = 0 ; while (j <>m_nNodeCount - 1) { int nMaxWeight = numeric_limitsint>::max () ; // 找到當前最短路徑 int i = 0 ; while (i <>m_nNodeCount) { if (!bFlag[i]) { ++ i ; continue ; } for (int j = 0; j <>m_nNodeCount; ++ j) { if (!bFlag[j] && nMaxWeight > m_nvGraph[i][j]) { nMaxWeight = m_nvGraph[i][j] ; nMaxIndexA = i ; nMaxIndexB = j ; } } ++ i ; } bFlag[nMaxIndexB] = true ; m_tnMSTree.push_back (TreeNode(nMaxIndexA, nMaxIndexB, nMaxWeight)) ; ++ j ; } // 輸出結(jié)果 /*for (vectorTreeNode>::const_iterator ite = m_tnMSTree.begin() ; ite != m_tnMSTree.end() ; ++ ite ) { cout <>(*ite).m_nVertexIndexA <>'->' <>(*ite).m_nVertexIndexB <>' : ' <>(*ite).m_nWeight <>endl ; }*/ } private: vectorvectorint> > m_nvGraph ; // 無向連通圖 vectorTreeNode> m_tnMSTree ; // 最小生成樹 int m_nNodeCount ; } ; class AA_TSP { public: AA_TSP (const vectorvectorint> >& vnGraph) { m_mstPrim.SetData(vnGraph) ; } void Get_AA_Path () { m_mstPrim.DoPrim () ; vectorTreeNode> mstree = m_mstPrim.GetMSTree () ; vectorvectorint> > graph = m_mstPrim.GetGraph() ; int iweight = 0 ; for (vectorTreeNode>::const_iterator ite = mstree.begin() ; ite != mstree.end() ; ++ ite ) { cout <>(*ite).m_nVertexIndexA <>'->' <>(*ite).m_nVertexIndexB <>' : ' <>(*ite).m_nWeight <>endl ; iweight += (*ite).m_nWeight ; } cout <>mstree[mstree.size()-1].m_nVertexIndexB <>'->' <>mstree[0].m_nVertexIndexA <>' : ' <>graph[mstree[0].m_nVertexIndexA][mstree[mstree.size()-1].m_nVertexIndexB] <>endl ; iweight += graph[mstree[0].m_nVertexIndexA][mstree[mstree.size()-1].m_nVertexIndexB] ; cout <>'Total weight: ' <>iweight <>endl ; } private: MST_Prim m_mstPrim ; }; int main() { const int cnNodeCount = 5 ; vectorvectorint> > graph (cnNodeCount) ; for (size_t i = 0; i <>graph.size() ; ++ i) { graph[i].resize (cnNodeCount, numeric_limitsint>::max()) ; } graph[0][1] = 5 ; graph[0][2] = 1 ; graph[0][3] = 2 ; graph[0][4] = 3 ; graph[1][0] = 5 ; graph[1][2] = 4 ; graph[1][3] = 2 ; graph[1][4] = 2 ; graph[2][1] = 4 ; graph[2][0] = 1 ; graph[2][3] = 5 ; graph[2][4] = 3 ; graph[3][1] = 2 ; graph[3][2] = 5 ; graph[3][0] = 2 ; graph[3][4] = 2 ; graph[4][1] = 2 ; graph[4][2] = 3 ; graph[4][3] = 2 ; graph[4][0] = 3 ; AA_TSP aa (graph) ; aa.Get_AA_Path () ; return 0 ; }
在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。
|
