一、圖靈機(jī)

根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個(gè)讀寫頭讀到的帶符號(hào)，圖靈機(jī)的一個(gè)計(jì)算步可實(shí)現(xiàn)下面3個(gè)操作之一或全部。

1. 改變有限狀態(tài)控制器中的狀態(tài)。

2. 清除當(dāng)前讀寫頭下的方格中原有帶符號(hào)并寫上新的帶符號(hào)。

3. 獨(dú)立地將任何一個(gè)或所有讀寫頭，向左移動(dòng)一個(gè)方格(L)或向右移動(dòng)一個(gè)方格(R)或停在當(dāng)前單元不動(dòng)(S)。

k帶圖靈機(jī)可形式化地描述為一個(gè)7元組(Q，T，I，δ，b，q0，qf)，其中: 

1. Q是有限個(gè)狀態(tài)的集合。

2. T是有限個(gè)帶符號(hào)的集合。

3. I是輸入符號(hào)的集合。

4. b是唯一的空白符，b∈T-I。

5. q0是初始狀態(tài)。      

6. qf是終止(或接受)狀態(tài)。

7. δ是移動(dòng)函數(shù)。

它是從Q×Tk的某一子集映射到Q×(T×{L，R，S})k的函數(shù)。

圖靈機(jī)M的時(shí)間復(fù)雜性T(n)是它處理所有長(zhǎng)度為n的輸入所需的最大計(jì)算步數(shù)。如果對(duì)某個(gè)長(zhǎng)度為n的輸入，圖靈機(jī)不停機(jī)，T(n)對(duì)這個(gè)n值無定義。

圖靈機(jī)的空間復(fù)雜性S(n)是它處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的總和。如果某個(gè)讀寫頭無限地向右移動(dòng)而不停機(jī)，S(n)也無定義。

確定型圖靈機(jī)

有限狀態(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類問題

一般地說，將可由多項(xiàng)式時(shí)間算法求解的問題看作是易處理的問題，而將需要超多項(xiàng)式時(shí)間才能求解的問題看作是難處理的問題。

有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項(xiàng)式時(shí)間算法，也沒有人能夠證明這些問題需要超多項(xiàng)式時(shí)間下界。

在圖靈機(jī)計(jì)算模型下，這類問題的計(jì)算復(fù)雜性至今未知。

為了研究這類問題的計(jì)算復(fù)雜性，人們提出了另一個(gè)能力更強(qiáng)的計(jì)算模型，即非確定性圖靈機(jī)計(jì)算模型，簡(jiǎn)記為NDTM(Nondeterministic Turing Machine)。

在非確定性圖靈機(jī)計(jì)算模型下，許多問題可以在多項(xiàng)式時(shí)間內(nèi)求解。

非確定性圖靈機(jī)

在圖靈機(jī)計(jì)算模型中，移動(dòng)函數(shù)δ是單值的，即對(duì)于Q′Tk中的每一個(gè)值，當(dāng)它屬于δ的定義域時(shí)，Q′(T′{L，R，S})k中只有唯一的值與之對(duì)應(yīng)，稱這種圖靈機(jī)為確定性圖靈機(jī)，簡(jiǎn)記為DTM(Deterministic Turing Machine)。

非確定性圖靈機(jī)(NDTM）：一個(gè)k帶的非確定性圖靈機(jī)M是一個(gè)7元組：(Q，T，I，δ，b，q0，qf)。與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動(dòng)函數(shù)δ具有不確定性，即對(duì)于Q×Tk中的每一個(gè)值(q;x1,x2,…,xk)，當(dāng)它屬于δ的定義域時(shí)，Q×(T×{L，R，S})k中有唯一的一個(gè)子集δ(q;x1,x2,…,xk)與之對(duì)應(yīng)?？梢栽讦?q;x1,x2,…,xk)中隨意選定一個(gè)值作為它的函數(shù)值。

P類與NP類語(yǔ)言定義

P={L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTM所接受的語(yǔ)言}

NP={L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言}

由于一臺(tái)確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)接受的語(yǔ)言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。故P í NP。 

NP類語(yǔ)言舉例——無向圖的團(tuán)問題

該問題的輸入是一個(gè)有n個(gè)頂點(diǎn)的無向圖G=(V，E)和一個(gè)整數(shù)k。要求判定圖G是否包含一個(gè)k頂點(diǎn)的完全子圖(團(tuán))，即判定是否存在V’V，|V’|=k，且對(duì)于所有的u，v∈V’，有(u，v)∈E。

若用鄰接矩陣表示圖G，用二進(jìn)制串表示整數(shù)k，則團(tuán)問題的一個(gè)實(shí)例可以用長(zhǎng)度為的二進(jìn)位串表示。因此，團(tuán)問題可表示為語(yǔ)言：

CLIQUE={w#v|w，v∈{0，1}*，以w為鄰接矩陣的圖G有一個(gè)k頂點(diǎn)的團(tuán)，其中v是k的二進(jìn)制表示。}

接受該語(yǔ)言CLIQUE的非確定性算法：用非確定性選擇指令選出包含k個(gè)頂點(diǎn)的候選頂點(diǎn)子集V，然后確定性地檢查該子集是否是團(tuán)問題的一個(gè)解。算法分為3個(gè)階段

算法的第一階段將輸入串w#v分解，并計(jì)算出n = ，以及用v表示的整數(shù)k。若輸入不具有形式w#v或|w|不是一個(gè)平方數(shù)就拒絕該輸入。顯而易見，第一階段可在時(shí)間內(nèi)完成。

在算法的第二階段中，非確定性地選擇V的一個(gè)k元子集V’V。

算法的第三階段是確定性地檢查V’的團(tuán)性質(zhì)。若V’是一個(gè)團(tuán)則接受輸入，否則拒絕輸入。這顯然可以在時(shí)間內(nèi)完成。因此，整個(gè)算法的時(shí)間復(fù)雜性為 。

非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語(yǔ)言CLIQUE，故CLIQUE∈NP.

NP完全問題

PNP。

直觀上看，P類問題是確定性計(jì)算模型下的易解問題類，而NP類問題是非確定性計(jì)算模型下的易驗(yàn)證問題類。

大多數(shù)的計(jì)算機(jī)科學(xué)家認(rèn)為NP類中包含了不屬于P類的語(yǔ)言，即P≠NP。

NP完全問題有一種令人驚奇的性質(zhì)，即如果一個(gè)NP完全問題能在多項(xiàng)式時(shí)間內(nèi)得到解決，那么NP中的每一個(gè)問題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P = NP。

目前還沒有一個(gè)NP完全問題有多項(xiàng)式時(shí)間算法。

三、NP完全問題的近似算法

迄今為止，所有的NP完全問題都還沒有多項(xiàng)式時(shí)間算法。

對(duì)于這類問題，通?？刹扇∫韵聨追N解題策略。

1. 只對(duì)問題的特殊實(shí)例求解

2. 用動(dòng)態(tài)規(guī)劃法或分支限界法求解

3. 用概率算法求解

4. 只求近似解

5. 用啟發(fā)式方法求解

近似算法的性能

若一個(gè)最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個(gè)近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比定義為。

在通常情況下，該性能比是問題輸入規(guī)模n的一個(gè)函數(shù)ρ(n)，即。

該近似算法的相對(duì)誤差定義為：。若對(duì)問題的輸入規(guī)模n，有一函數(shù)ε(n)使得則稱ε(n)為該近似算法的相對(duì)誤差界。近似算法的性能比ρ(n)與相對(duì)誤差界ε(n)之間顯然有如下關(guān)系：。

旅行售貨員問題近似算法

問題描述：給定一個(gè)完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。

旅行售貨員問題的一些特殊性質(zhì)：

比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)c就具有三角不等式性質(zhì)。

• 1 滿足三角不等式的旅行售貨員問題

對(duì)于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計(jì)找近似最優(yōu)的旅行售貨員回路的算法。

void approxTSP (Graph g)

{

1. 選擇g的任一頂點(diǎn)r；

2. 用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹T；

3. 前序遍歷樹T得到的頂點(diǎn)表L；

4. 將r加到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計(jì) 算結(jié)果返回；

}

當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過最優(yōu)旅行售貨員回路費(fèi)用的2倍。

實(shí)現(xiàn)

/* 主題：近似算法——旅行售貨員問題

* 作者：chinazhangjie

* 郵箱：chinajiezhang@gmail.com

* 開發(fā)語(yǔ)言： C++

* 開發(fā)環(huán)境： Virsual Studio 2005

* 時(shí)間: 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 ()

    {

        // 是否被訪問標(biāo)志

        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 () ;

            // 找到當(dāng)前最短路徑

            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 ;

}

• 2 一般的旅行售貨員問題

在費(fèi)用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項(xiàng)式時(shí)間近似算法，除非P=NP。換句話說，若P≠NP，則對(duì)任意常數(shù)ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項(xiàng)式時(shí)間近似算法。