計(jì)算機(jī)領(lǐng)域典型問題

1、 計(jì)算機(jī)領(lǐng)域典型問題 在人類社會(huì)的發(fā)展過程中，人們提出過許多具有深遠(yuǎn)意在人類社會(huì)的發(fā)展過程中，人們提出過許多具有深遠(yuǎn)意義的科學(xué)問題，其中對(duì)計(jì)算機(jī)學(xué)科一些分支領(lǐng)域的形成和義的科學(xué)問題，其中對(duì)計(jì)算機(jī)學(xué)科一些分支領(lǐng)域的形成和發(fā)展起了重要的作用。另外，在計(jì)算機(jī)學(xué)科的發(fā)展過程中，發(fā)展起了重要的作用。另外，在計(jì)算機(jī)學(xué)科的發(fā)展過程中，為了便于對(duì)計(jì)算機(jī)科學(xué)中有關(guān)問題和概念的本質(zhì)的理解，為了便于對(duì)計(jì)算機(jī)科學(xué)中有關(guān)問題和概念的本質(zhì)的理解，人們還給出了不少反映該學(xué)科某一方面本質(zhì)特征的典型實(shí)人們還給出了不少反映該學(xué)科某一方面本質(zhì)特征的典型實(shí)例，在這里一并歸于計(jì)算機(jī)學(xué)科的典型問題。例，在這里一并歸于計(jì)算機(jī)學(xué)科的典型問題

2、。 計(jì)算機(jī)學(xué)科典型問題的提出及研究，不僅有助于我們深計(jì)算機(jī)學(xué)科典型問題的提出及研究，不僅有助于我們深刻地理解計(jì)算機(jī)學(xué)科，而且還對(duì)學(xué)科的發(fā)展有著十分重要刻地理解計(jì)算機(jī)學(xué)科，而且還對(duì)學(xué)科的發(fā)展有著十分重要的推動(dòng)作用。的推動(dòng)作用。 n下面分別對(duì)圖論中有代表性的哥尼斯堡下面分別對(duì)圖論中有代表性的哥尼斯堡七橋問題，算法與算法復(fù)雜性領(lǐng)域中有七橋問題，算法與算法復(fù)雜性領(lǐng)域中有代表性的漢諾（代表性的漢諾（Hanoi Hanoi ）塔問題，算法）塔問題，算法復(fù)雜性中的難解性問題，證比求易算法，復(fù)雜性中的難解性問題，證比求易算法，旅行商問題與組合爆炸問題，哲學(xué)家共旅行商問題與組合爆炸問題，哲學(xué)家共餐問題餐問題,

3、,圖靈測(cè)試問題，博弈問題等問圖靈測(cè)試問題，博弈問題等問題及其相關(guān)內(nèi)容進(jìn)行分析。題及其相關(guān)內(nèi)容進(jìn)行分析。補(bǔ)充知識(shí)補(bǔ)充知識(shí) 計(jì)算機(jī)領(lǐng)域典型問題計(jì)算機(jī)領(lǐng)域典型問題n1歌尼斯堡七橋問題與哈密爾頓回路問題歌尼斯堡七橋問題與哈密爾頓回路問題n2漢諾塔問題漢諾塔問題n3算法復(fù)雜性中的難解性問題算法復(fù)雜性中的難解性問題n4哲學(xué)家共餐問題哲學(xué)家共餐問題n5旅行商問題旅行商問題n6圖靈測(cè)試問題圖靈測(cè)試問題n7搏弈問題搏弈問題1 歌尼斯堡七橋問題與哈密爾頓回路問題n 18 18世紀(jì)中葉，當(dāng)時(shí)東普魯士有一座哥尼斯堡（世紀(jì)中葉，當(dāng)時(shí)東普魯士有一座哥尼斯堡（KonigsbergKonigsberg）城，城中）城，城中有一

4、條貫穿全市的普雷格爾（有一條貫穿全市的普雷格爾（PregolPregol）河，河中央有座小島，叫奈佛夫）河，河中央有座小島，叫奈佛夫（KneiphofKneiphof）島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分成北區(qū)、）島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)東區(qū)、南區(qū)和島區(qū)4 4個(gè)區(qū)域，全城共有個(gè)區(qū)域，全城共有7 7座橋?qū)⒆鶚驅(qū)? 4個(gè)城區(qū)相連起來(lái)。個(gè)城區(qū)相連起來(lái)。 北區(qū)北區(qū)東區(qū)東區(qū)島區(qū)島區(qū) 南區(qū)南區(qū)圖圖1 1 哥尼斯堡七橋地理位置示意圖哥尼斯堡七橋地理位置示意圖n當(dāng)時(shí)該城市的人們熱衷一個(gè)難題：一個(gè)人怎樣不重復(fù)地走完七橋，最后回當(dāng)時(shí)該城市的人們熱衷一個(gè)難

5、題：一個(gè)人怎樣不重復(fù)地走完七橋，最后回到出發(fā)地點(diǎn)？即尋找走遍這到出發(fā)地點(diǎn)？即尋找走遍這7 7座橋，且只許走過每座橋一次，最后又回到原座橋，且只許走過每座橋一次，最后又回到原出發(fā)點(diǎn)的路徑。試驗(yàn)者都沒有解決這個(gè)難題。出發(fā)點(diǎn)的路徑。試驗(yàn)者都沒有解決這個(gè)難題。17361736年，瑞士數(shù)學(xué)家列昂納年，瑞士數(shù)學(xué)家列昂納德德歐拉（歐拉（L.EulerL.Euler）發(fā)表圖論的首篇論文，論證了該問題無(wú)解，即從一點(diǎn)）發(fā)表圖論的首篇論文，論證了該問題無(wú)解，即從一點(diǎn)出發(fā)不重復(fù)地走遍七橋，最后又回到原來(lái)出發(fā)點(diǎn)是不可能的。他論證所用出發(fā)不重復(fù)地走遍七橋，最后又回到原來(lái)出發(fā)點(diǎn)是不可能的。他論證所用的圖為圖的圖為圖2 2所

6、示。后人為了紀(jì)念數(shù)學(xué)家歐拉，將這個(gè)難題稱為所示。后人為了紀(jì)念數(shù)學(xué)家歐拉，將這個(gè)難題稱為“哥尼斯堡七哥尼斯堡七橋問題橋問題”。圖圖2 2 哥尼斯哥尼斯堡七橋問題堡七橋問題示意圖示意圖CBDAn為了解決哥尼斯堡七橋問題，歐拉用為了解決哥尼斯堡七橋問題，歐拉用4 4個(gè)字母?jìng)€(gè)字母A A、B B、C C、D D代表代表4 4個(gè)城個(gè)城區(qū)，并用區(qū)，并用7 7條線表示條線表示7 7座橋，如圖座橋，如圖2 2所示。在圖中，只有所示。在圖中，只有4 4個(gè)點(diǎn)和個(gè)點(diǎn)和7 7條條線，這樣做是基于該問題本質(zhì)的考慮，抽象出問題最本質(zhì)的東西，線，這樣做是基于該問題本質(zhì)的考慮，抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西（如橋

7、的長(zhǎng)度等），從而將哥尼斯堡七橋問忽視問題非本質(zhì)的東西（如橋的長(zhǎng)度等），從而將哥尼斯堡七橋問題抽象成為一個(gè)數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題抽象成為一個(gè)數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。歐拉在論文中論證了這樣的回路是不存在的，后來(lái)，人們把題了。歐拉在論文中論證了這樣的回路是不存在的，后來(lái)，人們把有這樣回路的圖稱為歐拉圖。有這樣回路的圖稱為歐拉圖。 n將其有經(jīng)過所有邊的簡(jiǎn)單生成回路的圖稱為歐拉圖將其有經(jīng)過所有邊的簡(jiǎn)單生成回路的圖稱為歐拉圖n歐拉不僅給出了哥尼斯堡七橋問題的證明，還將問題進(jìn)行了一般歐拉不僅給出了哥尼斯堡七橋問題的證明，還將問題進(jìn)行了一般化處理，即對(duì)給定的任

8、意一個(gè)河道圖與任意多座橋，判定可能不化處理，即對(duì)給定的任意一個(gè)河道圖與任意多座橋，判定可能不可能每座橋恰好走過一次，并用數(shù)學(xué)方法給出了可能每座橋恰好走過一次，并用數(shù)學(xué)方法給出了3 3條判定規(guī)則：條判定規(guī)則：（1 1）如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路線是找不到）如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路線是找不到的；的；（2 2）如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，）如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路線；找到所要求的路線；（3 3）如果沒有一個(gè)地方是通奇數(shù)座橋的，則無(wú)論從哪里出發(fā)，所）如果沒有一個(gè)地方是通奇數(shù)座橋的，則無(wú)論從哪里出發(fā)，

9、所要求的路線都能實(shí)現(xiàn)。要求的路線都能實(shí)現(xiàn)。 歐拉的論文為圖論的形成奠定了基礎(chǔ)。今天，圖論已廣泛地應(yīng)用歐拉的論文為圖論的形成奠定了基礎(chǔ)。今天，圖論已廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、信息論、控制論等科學(xué)之中，并已成為我們于計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、信息論、控制論等科學(xué)之中，并已成為我們對(duì)現(xiàn)實(shí)問題進(jìn)行抽象的一個(gè)強(qiáng)有力的數(shù)學(xué)工具。隨著計(jì)算機(jī)科學(xué)的發(fā)對(duì)現(xiàn)實(shí)問題進(jìn)行抽象的一個(gè)強(qiáng)有力的數(shù)學(xué)工具。隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論在計(jì)算機(jī)科學(xué)中的作用越來(lái)越大，同時(shí)，圖論本身也得到了展，圖論在計(jì)算機(jī)科學(xué)中的作用越來(lái)越大，同時(shí)，圖論本身也得到了充分的發(fā)展。充分的發(fā)展。 n在圖論中除了歐拉回路以外，在圖論中除了歐拉回路以外，還有

10、一個(gè)著名的還有一個(gè)著名的“哈密爾頓回哈密爾頓回路問題路問題”。十九世紀(jì)愛爾蘭數(shù)。十九世紀(jì)愛爾蘭數(shù)學(xué)家哈密爾頓學(xué)家哈密爾頓(Hamilton)(Hamilton)發(fā)明發(fā)明了一種叫做周游世界的數(shù)學(xué)游了一種叫做周游世界的數(shù)學(xué)游戲。它的玩法是：給你一個(gè)正戲。它的玩法是：給你一個(gè)正十二面體，它有二十個(gè)頂點(diǎn)，十二面體，它有二十個(gè)頂點(diǎn)，把每個(gè)頂點(diǎn)看做一個(gè)城市，把把每個(gè)頂點(diǎn)看做一個(gè)城市，把正十二面體的三十條棱看成連正十二面體的三十條棱看成連接這些城市的路。請(qǐng)你找一條接這些城市的路。請(qǐng)你找一條從某城市出發(fā)，經(jīng)過每個(gè)城市從某城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，并且最后回到出發(fā)恰好一次，并且最后回到出發(fā)點(diǎn)的路線。我們把

11、正十二面體點(diǎn)的路線。我們把正十二面體投影到平面上，在圖投影到平面上，在圖3 3中標(biāo)出了中標(biāo)出了一種走法，即從城市一種走法，即從城市1 1出發(fā)，經(jīng)出發(fā)，經(jīng)過過2 2，3 3，2020，最后回到，最后回到1 1。2019181716111213151098123146547圖圖3 3周游世界游戲示意圖周游世界游戲示意圖n “ “哈密爾頓回路問題哈密爾頓回路問題”與與“歐拉回路問題歐拉回路問題”看上去十分相似，然而又是完全不同的兩個(gè)問題。看上去十分相似，然而又是完全不同的兩個(gè)問題。“哈密爾頓回路問題哈密爾頓回路問題”是訪問每個(gè)結(jié)點(diǎn)一次，而是訪問每個(gè)結(jié)點(diǎn)一次，而“歐拉回路問題歐拉回路問題”是訪問每條邊

12、一次。對(duì)圖是訪問每條邊一次。對(duì)圖G G是否是否存在存在“歐拉回路歐拉回路”前面已給出充分必要條件，而前面已給出充分必要條件，而對(duì)圖對(duì)圖G G是否存在是否存在“哈密爾頓回路哈密爾頓回路”至今仍未找到滿至今仍未找到滿足該問題的充分必要條件。足該問題的充分必要條件。 2漢諾塔問題n 傳說(shuō)在古代印度的貝拿勒斯神廟里安放了一塊傳說(shuō)在古代印度的貝拿勒斯神廟里安放了一塊黃銅座，座上豎有三根寶石柱子。在第一根寶石柱上，按黃銅座，座上豎有三根寶石柱子。在第一根寶石柱上，按照從小到大、自上而下的順序放有照從小到大、自上而下的順序放有6464個(gè)直徑大小不一的金個(gè)直徑大小不一的金盤子，形成一座金塔，如圖盤子，形成一座

13、金塔，如圖4 44 4所示，即所謂的漢諾塔所示，即所謂的漢諾塔（又稱梵天塔）。天神讓廟里的僧侶們將第一根柱子上的（又稱梵天塔）。天神讓廟里的僧侶們將第一根柱子上的6464個(gè)盤子借助第二根柱子全部移到第三根柱子上，即將整個(gè)盤子借助第二根柱子全部移到第三根柱子上，即將整個(gè)塔遷移，同時(shí)定下個(gè)塔遷移，同時(shí)定下3 3條規(guī)則：條規(guī)則：n n （1 1）每次只能移動(dòng)一個(gè)盤子；）每次只能移動(dòng)一個(gè)盤子；n （2 2）盤子只能在三根柱子上來(lái)回移動(dòng)，不能放在）盤子只能在三根柱子上來(lái)回移動(dòng)，不能放在他處；他處；n （3 3）在移動(dòng)過程中，三根柱子上的盤子必須始終）在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小

14、盤在上。圖保持大盤在下，小盤在上。圖4 4漢諾塔問題示意圖漢諾塔問題示意圖6464個(gè)盤子個(gè)盤子6363個(gè)盤子個(gè)盤子n 據(jù)說(shuō)當(dāng)這據(jù)說(shuō)當(dāng)這6464個(gè)盤子全部移到第三根柱子上后，個(gè)盤子全部移到第三根柱子上后，世界末日就要到了。這就是著名的漢諾塔塔問題。世界末日就要到了。這就是著名的漢諾塔塔問題。圖圖4 4漢諾塔問題示意圖漢諾塔問題示意圖6 4 個(gè)個(gè)盤子盤子6 3 個(gè)個(gè)盤子盤子n 用計(jì)算機(jī)求解一個(gè)實(shí)際問題，首先要從這個(gè)實(shí)際問題用計(jì)算機(jī)求解一個(gè)實(shí)際問題，首先要從這個(gè)實(shí)際問題中抽象出一個(gè)數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算中抽象出一個(gè)數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后根據(jù)算法編寫程序，經(jīng)過調(diào)

15、試和運(yùn)行，從而完成法，最后根據(jù)算法編寫程序，經(jīng)過調(diào)試和運(yùn)行，從而完成該問題的求解。從實(shí)際問題抽象出一個(gè)數(shù)學(xué)模型的實(shí)質(zhì)，該問題的求解。從實(shí)際問題抽象出一個(gè)數(shù)學(xué)模型的實(shí)質(zhì)，其實(shí)就是要用數(shù)學(xué)的方法抽取問題主要的、本質(zhì)的內(nèi)容，其實(shí)就是要用數(shù)學(xué)的方法抽取問題主要的、本質(zhì)的內(nèi)容，最終實(shí)現(xiàn)對(duì)該問題的正確認(rèn)識(shí)。最終實(shí)現(xiàn)對(duì)該問題的正確認(rèn)識(shí)。n 漢諾塔問題是一個(gè)典型的用遞歸方法來(lái)解決的問題。漢諾塔問題是一個(gè)典型的用遞歸方法來(lái)解決的問題。遞歸是計(jì)算機(jī)學(xué)科中的一個(gè)重要概念。所謂遞歸，就是遞歸是計(jì)算機(jī)學(xué)科中的一個(gè)重要概念。所謂遞歸，就是將一個(gè)較大的問題歸約為一個(gè)或多個(gè)子問題的求解方法。將一個(gè)較大的問題歸約為一個(gè)或多個(gè)子

16、問題的求解方法。而這些子問題比原問題簡(jiǎn)單，且在結(jié)構(gòu)上與原問題相同。而這些子問題比原問題簡(jiǎn)單，且在結(jié)構(gòu)上與原問題相同。n 根據(jù)遞歸方法，我們可以將根據(jù)遞歸方法，我們可以將6464個(gè)盤子的漢諾塔問題個(gè)盤子的漢諾塔問題轉(zhuǎn)化為求解轉(zhuǎn)化為求解6363個(gè)盤子的漢諾塔問題，如果個(gè)盤子的漢諾塔問題，如果6363個(gè)盤子的漢個(gè)盤子的漢諾塔問題能夠解決，則可以將諾塔問題能夠解決，則可以將6363個(gè)盤子先移動(dòng)到第二個(gè)個(gè)盤子先移動(dòng)到第二個(gè)柱子上，再將最后一個(gè)盤子直接移動(dòng)到第三個(gè)柱子上，柱子上，再將最后一個(gè)盤子直接移動(dòng)到第三個(gè)柱子上，最后又一次將最后又一次將6363個(gè)盤子從第二個(gè)柱子移動(dòng)到第三個(gè)柱子個(gè)盤子從第二個(gè)柱子移動(dòng)

17、到第三個(gè)柱子上。上。n如圖如圖4 4所示，則可以解決所示，則可以解決6464個(gè)盤子的漢諾塔問題。依個(gè)盤子的漢諾塔問題。依此類推，此類推，6363個(gè)盤子的漢諾塔求解問題可以轉(zhuǎn)化為個(gè)盤子的漢諾塔求解問題可以轉(zhuǎn)化為6262個(gè)盤子的漢諾塔求解問題，個(gè)盤子的漢諾塔求解問題，6262個(gè)盤子的漢諾塔求解個(gè)盤子的漢諾塔求解問題又可以轉(zhuǎn)化為問題又可以轉(zhuǎn)化為6161個(gè)盤子的漢諾塔求解問題，直個(gè)盤子的漢諾塔求解問題，直到到1 1個(gè)盤子的漢諾塔求解問題。再由個(gè)盤子的漢諾塔求解問題。再由1 1個(gè)盤子的漢諾個(gè)盤子的漢諾塔的解求出塔的解求出2 2個(gè)盤子的漢諾塔，直到解出個(gè)盤子的漢諾塔，直到解出6464個(gè)盤子的個(gè)盤子的漢諾塔

18、問題。漢諾塔問題。 按照上面的算法，按照上面的算法，n n個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)是數(shù)是n-1n-1個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)的個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)的2 2倍加倍加1 1。于是于是 h(n)=2h(n-1)+1h(n)=2h(n-1)+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =23h(n-3)+22+2+1 =23h(n-3)+22+2+1 = = =2nh(0)+2n-1+ =2nh(0)+2n-1+22+2+1+22+2+1 =2n-1+ =2n-

19、1+22+2+1+22+2+1 =2n-1 =2n-1因此，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為：因此，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為： 264-1=18446744073709551615 264-1=18446744073709551615 如果每秒移動(dòng)一次，一年有如果每秒移動(dòng)一次，一年有3153600031536000秒，則僧侶們秒，則僧侶們一刻不停地來(lái)回搬動(dòng)，也需要花費(fèi)大約一刻不停地來(lái)回搬動(dòng)，也需要花費(fèi)大約58495849億年的億年的時(shí)間。假定計(jì)算機(jī)以每秒時(shí)間。假定計(jì)算機(jī)以每秒10001000萬(wàn)個(gè)盤子的速度進(jìn)行萬(wàn)個(gè)盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約搬遷，則需要花費(fèi)大約58

20、49058490年的時(shí)間。年的時(shí)間。3算法復(fù)雜性中的難解性問題n算法分析是計(jì)算機(jī)科學(xué)的一項(xiàng)主要工作。為了進(jìn)行算法算法分析是計(jì)算機(jī)科學(xué)的一項(xiàng)主要工作。為了進(jìn)行算法比較，我們必須給出算法效率的某種衡量標(biāo)準(zhǔn)。比較，我們必須給出算法效率的某種衡量標(biāo)準(zhǔn)。n假設(shè)假設(shè)M M是一種算法，并設(shè)是一種算法，并設(shè)n n為輸入數(shù)據(jù)的規(guī)模。實(shí)施為輸入數(shù)據(jù)的規(guī)模。實(shí)施M M所占所占用的時(shí)間和空間是衡量該算法效率的兩個(gè)主要指標(biāo)。時(shí)用的時(shí)間和空間是衡量該算法效率的兩個(gè)主要指標(biāo)。時(shí)間由間由“操作操作”次數(shù)衡量。比如，對(duì)于排序和查找，我們次數(shù)衡量。比如，對(duì)于排序和查找，我們對(duì)比較次數(shù)計(jì)數(shù)?？臻g由實(shí)施該算法所需的最大內(nèi)存來(lái)對(duì)比較次

21、數(shù)計(jì)數(shù)?？臻g由實(shí)施該算法所需的最大內(nèi)存來(lái)衡量。衡量。 n算法算法M M的復(fù)雜性是一個(gè)函數(shù)的復(fù)雜性是一個(gè)函數(shù)(n(n) )，它對(duì)于輸人數(shù)據(jù)的規(guī)模，它對(duì)于輸人數(shù)據(jù)的規(guī)模n n給出運(yùn)行該算法所需時(shí)間與所需存儲(chǔ)空間。執(zhí)行一個(gè)算給出運(yùn)行該算法所需時(shí)間與所需存儲(chǔ)空間。執(zhí)行一個(gè)算法所需存儲(chǔ)空間通常就是數(shù)據(jù)規(guī)模的倍數(shù)。因此，除非法所需存儲(chǔ)空間通常就是數(shù)據(jù)規(guī)模的倍數(shù)。因此，除非特殊情況，特殊情況，“復(fù)雜性復(fù)雜性”將指運(yùn)行算法的時(shí)間。將指運(yùn)行算法的時(shí)間。 對(duì)于時(shí)間復(fù)雜性函數(shù)對(duì)于時(shí)間復(fù)雜性函數(shù)(n)(n)。它通常不僅僅與輸入。它通常不僅僅與輸入數(shù)據(jù)的規(guī)模有關(guān)，還與特定的數(shù)據(jù)有關(guān)。例如，在一篇數(shù)據(jù)的規(guī)模有關(guān)，還與特定

22、的數(shù)據(jù)有關(guān)。例如，在一篇英文短文中查找第一次出現(xiàn)的英文短文中查找第一次出現(xiàn)的3 3個(gè)字母的單詞個(gè)字母的單詞W W。那么，。那么，如果如果W W為定冠詞為定冠詞“the”the”，則，則W W很可能在短文的開頭部分出很可能在短文的開頭部分出現(xiàn)，于是現(xiàn)，于是(n)(n)值將會(huì)比較??；如果值將會(huì)比較??；如果W W是單詞是單詞“axeaxe，”，則則W W甚至可能不會(huì)在短文中出現(xiàn)，所以甚至可能不會(huì)在短文中出現(xiàn)，所以(n)(n)可能會(huì)很大。可能會(huì)很大。 因此，考慮對(duì)于適當(dāng)?shù)那闆r，求出復(fù)雜性函數(shù)因此，考慮對(duì)于適當(dāng)?shù)那闆r，求出復(fù)雜性函數(shù)(n)(n)。在復(fù)雜性理論中研究得最多的兩種情況是：。在復(fù)雜性理論中研究

23、得最多的兩種情況是： (1)(1)最壞情況最壞情況 對(duì)于任何可能的輸入，對(duì)于任何可能的輸入，(n)(n)的最大值。的最大值。 (2)(2)平均情況平均情況 (n)(n)的期望值。的期望值。 假定假定M M是一個(gè)算法，并設(shè)是一個(gè)算法，并設(shè)n n為輸入數(shù)據(jù)的大小。顯然為輸入數(shù)據(jù)的大小。顯然M M的復(fù)的復(fù)雜性雜性(n)(n)隨著隨著n n的增大而增大。通常我們需要考察的是的增大而增大。通常我們需要考察的是(n)(n)的增長(zhǎng)率，這常常由的增長(zhǎng)率，這常常由(n)(n)與某標(biāo)準(zhǔn)函數(shù)相比較而得，例如與某標(biāo)準(zhǔn)函數(shù)相比較而得，例如 loglog2 2n nn n， n logn log2 2n n， n n2

24、2， n n3 3， 2 2n n 等等，都可被用作為標(biāo)準(zhǔn)函數(shù)，這些函數(shù)是按其增長(zhǎng)等等，都可被用作為標(biāo)準(zhǔn)函數(shù)，這些函數(shù)是按其增長(zhǎng)率列出的：對(duì)數(shù)函數(shù)率列出的：對(duì)數(shù)函數(shù)log2nlog2n增長(zhǎng)最慢，指數(shù)函數(shù)增長(zhǎng)最慢，指數(shù)函數(shù)2n2n增長(zhǎng)最增長(zhǎng)最快，而多項(xiàng)式函數(shù)快，而多項(xiàng)式函數(shù)ncnc的增長(zhǎng)率隨其指數(shù)的增長(zhǎng)率隨其指數(shù)c c的增大而變快。的增大而變快。 將復(fù)雜性函數(shù)與一個(gè)標(biāo)準(zhǔn)函數(shù)相比較的一種方法是利將復(fù)雜性函數(shù)與一個(gè)標(biāo)準(zhǔn)函數(shù)相比較的一種方法是利用用“大大O”記號(hào)，我們給出它的定義：記號(hào)，我們給出它的定義： 設(shè)設(shè)(x(x) )與與g(xg(x) )為定義于為定義于R R或或R R的子集上的任意兩個(gè)函的子

25、集上的任意兩個(gè)函數(shù)。我們說(shuō)數(shù)。我們說(shuō)“(x(x) )與與g(xg(x) )同階同階”，記作，記作 (x(x) )O(g(g(g(g)。 如果存在實(shí)數(shù)如果存在實(shí)數(shù)k k和正常數(shù)和正常數(shù)C C使得對(duì)于所有的使得對(duì)于所有的x xk k有有 | |(x)| C |g(x)|(x)| C |g(x)|。如如 n n2 2+n+1=O(n+n+1=O(n2 2) )，該表達(dá)式表示，當(dāng)，該表達(dá)式表示，當(dāng)n n足夠大時(shí)表達(dá)式左邊約足夠大時(shí)表達(dá)式左邊約等于等于n n2 2。常見的大常見的大O O表示形式有：表示形式有： O(1)(1)稱為常數(shù)級(jí)；稱為常數(shù)級(jí)； O(logn)(logn)稱為對(duì)數(shù)級(jí)；稱為對(duì)數(shù)級(jí)；

26、O(n)(n)稱為線性級(jí)；稱為線性級(jí)； O(nc)(nc)稱為多項(xiàng)式級(jí)；稱為多項(xiàng)式級(jí)； O(c(cn n) )稱為指數(shù)級(jí)；稱為指數(shù)級(jí)； O(n!)(n!)稱為階乘級(jí)。稱為階乘級(jí)。 用以上表示方法，在漢諾塔問題中，需要移用以上表示方法，在漢諾塔問題中，需要移動(dòng)的盤子次數(shù)為動(dòng)的盤子次數(shù)為h(n)= 2n-1h(n)= 2n-1，則該問題的算法時(shí)間，則該問題的算法時(shí)間復(fù)雜度表示為復(fù)雜度表示為O(2n)(2n)。 一個(gè)問題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式一個(gè)問題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式（如指數(shù)函數(shù)）時(shí)，算法的執(zhí)行時(shí)間將隨（如指數(shù)函數(shù)）時(shí)，算法的執(zhí)行時(shí)間將隨n n的增加而急的增加而急劇增長(zhǎng)，以致即使

27、是中等規(guī)模的問題也不能求解出來(lái)，劇增長(zhǎng)，以致即使是中等規(guī)模的問題也不能求解出來(lái)，于是在計(jì)算復(fù)雜性中，將這一類問題稱為難解性問題。于是在計(jì)算復(fù)雜性中，將這一類問題稱為難解性問題。 為了更好地理解計(jì)算及其復(fù)雜性的有關(guān)概念，我為了更好地理解計(jì)算及其復(fù)雜性的有關(guān)概念，我國(guó)學(xué)者洪加威曾經(jīng)講了一個(gè)被人稱為國(guó)學(xué)者洪加威曾經(jīng)講了一個(gè)被人稱為“證比求易算法證比求易算法”的童話，用來(lái)幫助讀者理解計(jì)算復(fù)雜性的有關(guān)概念，具的童話，用來(lái)幫助讀者理解計(jì)算復(fù)雜性的有關(guān)概念，具體內(nèi)容如下。體內(nèi)容如下。 很久以前，有一個(gè)年輕的國(guó)王，名叫艾述。他酷很久以前，有一個(gè)年輕的國(guó)王，名叫艾述。他酷愛數(shù)學(xué)，聘請(qǐng)了當(dāng)時(shí)最有名的數(shù)學(xué)家孔喚石當(dāng)

28、宰相。愛數(shù)學(xué)，聘請(qǐng)了當(dāng)時(shí)最有名的數(shù)學(xué)家孔喚石當(dāng)宰相。 鄰國(guó)有一位聰明美麗的公主，名字叫秋碧貞楠。鄰國(guó)有一位聰明美麗的公主，名字叫秋碧貞楠。艾述國(guó)王愛上了這位鄰國(guó)公主，便親自登門求婚。艾述國(guó)王愛上了這位鄰國(guó)公主，便親自登門求婚。 公主說(shuō)：公主說(shuō)：“你如果向我求婚，請(qǐng)你先求出你如果向我求婚，請(qǐng)你先求出48 770 48 770 428 433 377 171428 433 377 171的一個(gè)真因子，一天之內(nèi)交卷。的一個(gè)真因子，一天之內(nèi)交卷?！?” 艾艾述聽罷，心中暗喜，心想：我從述聽罷，心中暗喜，心想：我從2 2開始，一個(gè)一個(gè)地試，開始，一個(gè)一個(gè)地試，看看能不能除盡這個(gè)數(shù)，還怕找不到這個(gè)真因子嗎

29、？看看能不能除盡這個(gè)數(shù)，還怕找不到這個(gè)真因子嗎？ 艾述國(guó)王十分精于計(jì)算，他一秒鐘就算完一個(gè)數(shù)。艾述國(guó)王十分精于計(jì)算，他一秒鐘就算完一個(gè)數(shù)?？墒?，他從早到晚，共算了三萬(wàn)多個(gè)數(shù)，最終還是沒有可是，他從早到晚，共算了三萬(wàn)多個(gè)數(shù)，最終還是沒有結(jié)果。國(guó)王向公主求情，公主將答案相告：結(jié)果。國(guó)王向公主求情，公主將答案相告：223 092 223 092 827827是它的一個(gè)真因子。國(guó)王很快就驗(yàn)證了這個(gè)數(shù)確能是它的一個(gè)真因子。國(guó)王很快就驗(yàn)證了這個(gè)數(shù)確能除盡除盡48 770 428 433 377 17148 770 428 433 377 171。公主說(shuō)：公主說(shuō)：“我再給你一次機(jī)會(huì)，如果還求不出，將來(lái)你我再

30、給你一次機(jī)會(huì)，如果還求不出，將來(lái)你只好做我的證婚人了只好做我的證婚人了”。國(guó)王立即回國(guó)，召見宰相。國(guó)王立即回國(guó)，召見宰相孔喚石，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為孔喚石，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為1717位，如果這個(gè)數(shù)可以分成兩個(gè)真因子的乘積，則最位，如果這個(gè)數(shù)可以分成兩個(gè)真因子的乘積，則最小的一個(gè)真因子不會(huì)超過小的一個(gè)真因子不會(huì)超過9 9位。于是他給國(guó)王出了一位。于是他給國(guó)王出了一個(gè)主意：按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)主意：按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)號(hào)發(fā)下去，等公主給出數(shù)目后，立即將它們通報(bào)個(gè)號(hào)發(fā)下去，等公主給出數(shù)目后，立即將它們通報(bào)全國(guó)，讓每個(gè)老百姓用自己的編號(hào)

31、去除這個(gè)數(shù)，除全國(guó)，讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù)，除盡了立即上報(bào)，賞黃金萬(wàn)兩。盡了立即上報(bào)，賞黃金萬(wàn)兩。 于是，國(guó)王發(fā)動(dòng)全國(guó)上下的民眾，再度求婚，終于取于是，國(guó)王發(fā)動(dòng)全國(guó)上下的民眾，再度求婚，終于取得成功。得成功。 在在“證比求易算法證比求易算法”的故事中，國(guó)王最先使用的是一的故事中，國(guó)王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時(shí)間方面，后來(lái)由宰相提出種順序算法，其復(fù)雜性表現(xiàn)在時(shí)間方面，后來(lái)由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們認(rèn)為順序算法解決不了的問題完全可以用并行算法來(lái)我們認(rèn)為順序算法解決不了的問題完全可以用

32、并行算法來(lái)解決，甚至?xí)?，并行?jì)算機(jī)系統(tǒng)求解問題的速度將隨著解決，甚至?xí)?，并行?jì)算機(jī)系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實(shí)這是一種誤解。其實(shí)這是一種誤解。 當(dāng)將一個(gè)問題分解到多個(gè)處理器上解決時(shí)，由于算法當(dāng)將一個(gè)問題分解到多個(gè)處理器上解決時(shí)，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計(jì)算機(jī)系統(tǒng)的加速能力。下面，用阿達(dá)爾制了并行計(jì)算機(jī)系統(tǒng)的加速能力。下面，用阿達(dá)爾（G.AmdahlG.Amdahl）定律來(lái)說(shuō)明這個(gè)問題。）定律來(lái)說(shuō)明這個(gè)

33、問題。 設(shè)設(shè)f f為求解某個(gè)問題的計(jì)算中存在的必須串行執(zhí)行的為求解某個(gè)問題的計(jì)算中存在的必須串行執(zhí)行的操作占整個(gè)計(jì)算的百分比，操作占整個(gè)計(jì)算的百分比，p p為處理器的數(shù)目，為處理器的數(shù)目，SpSp為并為并行計(jì)算機(jī)系統(tǒng)最大的加速能力（單位：倍），則行計(jì)算機(jī)系統(tǒng)最大的加速能力（單位：倍），則Sp 1f +1- -fp 設(shè)設(shè)f=1%f=1%，pp，則，則Sp=100Sp=100。這說(shuō)明即使在并行。這說(shuō)明即使在并行計(jì)算機(jī)系統(tǒng)中有無(wú)窮多個(gè)處理器，解決這個(gè)串行執(zhí)行操計(jì)算機(jī)系統(tǒng)中有無(wú)窮多個(gè)處理器，解決這個(gè)串行執(zhí)行操作僅占全部操作作僅占全部操作1%1%的問題，其解題速度與單處理器的計(jì)的問題，其解題速度與單處理

34、器的計(jì)算機(jī)相比最多也只能提高一百倍。因此，對(duì)難解性問題算機(jī)相比最多也只能提高一百倍。因此，對(duì)難解性問題而言，單純的提高計(jì)算機(jī)系統(tǒng)的速度是遠(yuǎn)遠(yuǎn)不夠的，而而言，單純的提高計(jì)算機(jī)系統(tǒng)的速度是遠(yuǎn)遠(yuǎn)不夠的，而降低算法復(fù)雜度的數(shù)量級(jí)才是最關(guān)鍵的問題。降低算法復(fù)雜度的數(shù)量級(jí)才是最關(guān)鍵的問題。 國(guó)王有眾多百姓的幫助，求親成功是自然的事。但國(guó)王有眾多百姓的幫助，求親成功是自然的事。但是，如果換成是一個(gè)貧民百姓的小伙子去求婚，那就困是，如果換成是一個(gè)貧民百姓的小伙子去求婚，那就困難了。不過，小伙子可以從國(guó)王求親取得成功所采用的難了。不過，小伙子可以從國(guó)王求親取得成功所采用的并行算法中得到一個(gè)啟發(fā)，那就是：他可以隨

35、便猜一個(gè)并行算法中得到一個(gè)啟發(fā)，那就是：他可以隨便猜一個(gè)數(shù)，然后驗(yàn)證這個(gè)數(shù)。當(dāng)然，這樣做成功的可能性很小，數(shù)，然后驗(yàn)證這個(gè)數(shù)。當(dāng)然，這樣做成功的可能性很小，不過，萬(wàn)一小伙子運(yùn)氣好猜著了呢？由于一個(gè)數(shù)和它的不過，萬(wàn)一小伙子運(yùn)氣好猜著了呢？由于一個(gè)數(shù)和它的因子之間存在一些有規(guī)律的聯(lián)系，因此，數(shù)論知識(shí)水平因子之間存在一些有規(guī)律的聯(lián)系，因此，數(shù)論知識(shí)水平較高的人猜中的可能性就大。較高的人猜中的可能性就大。 我們說(shuō)，這個(gè)小伙子使用的算法叫做非確定性算法。我們說(shuō)，這個(gè)小伙子使用的算法叫做非確定性算法。這樣的算法需要有一種假想但實(shí)際并不存在的非確定性計(jì)這樣的算法需要有一種假想但實(shí)際并不存在的非確定性計(jì)算機(jī)才

36、能運(yùn)行，其理論上的計(jì)算模型是非確定性圖靈機(jī)。算機(jī)才能運(yùn)行，其理論上的計(jì)算模型是非確定性圖靈機(jī)。 在算法計(jì)算復(fù)雜性的研究中，將所有可以在多項(xiàng)式時(shí)在算法計(jì)算復(fù)雜性的研究中，將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為間內(nèi)求解的問題稱為P P類問題，而將所有在多項(xiàng)式時(shí)間內(nèi)類問題，而將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題稱為可以驗(yàn)證的問題稱為NPNP類問題，由于類問題，由于P P類問題采用的是確類問題采用的是確定性算法，定性算法，NPNP類問題采用的是非確定性算法，確定性算法類問題采用的是非確定性算法，確定性算法是非確定性算法的一個(gè)特例，因此是非確定性算法的一個(gè)特例，因此P PNPNP。 對(duì)于大多數(shù)實(shí)際問題來(lái)說(shuō)

37、，找到一個(gè)解可能很難，檢對(duì)于大多數(shù)實(shí)際問題來(lái)說(shuō)，找到一個(gè)解可能很難，檢驗(yàn)一個(gè)解常常比較容易，所以都屬于驗(yàn)一個(gè)解常常比較容易，所以都屬于NPNP類問題?，F(xiàn)在計(jì)算類問題?，F(xiàn)在計(jì)算機(jī)科學(xué)研究中一個(gè)懸而未決的重要問題是機(jī)科學(xué)研究中一個(gè)懸而未決的重要問題是P=?NPP=?NP。到目前。到目前為止，已經(jīng)發(fā)現(xiàn)了一批可計(jì)算但有相當(dāng)難度的問題是屬于為止，已經(jīng)發(fā)現(xiàn)了一批可計(jì)算但有相當(dāng)難度的問題是屬于NPNP類問題，并且常通過證明一個(gè)問題與已知屬于類問題，并且常通過證明一個(gè)問題與已知屬于NPNP類中的類中的某個(gè)問題等價(jià)，將其歸入某個(gè)問題等價(jià)，將其歸入NPNP類問題。類問題。 不過，該問題是否屬于不過，該問題是否屬于

38、P P類問題，即是否能找到多項(xiàng)式時(shí)類問題，即是否能找到多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法求解該問題，或證明該問題不存在多項(xiàng)式間計(jì)算復(fù)雜性算法求解該問題，或證明該問題不存在多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法求解，至今尚未解決。時(shí)間計(jì)算復(fù)雜性算法求解，至今尚未解決。2020世紀(jì)世紀(jì)7070年代初，年代初，庫(kù)克（庫(kù)克（S.A.CookS.A.Cook）和卡爾普（）和卡爾普（R.M.KarpR.M.Karp）在）在P=?NPP=?NP問題上取得問題上取得重大進(jìn)展，指出重大進(jìn)展，指出NPNP類中有一小類問題具有以下性質(zhì)：迄今為類中有一小類問題具有以下性質(zhì)：迄今為止，這些問題多數(shù)還沒有人找到多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法。止，這些

39、問題多數(shù)還沒有人找到多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法。但是，一旦其中的一個(gè)問題找到了多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算但是，一旦其中的一個(gè)問題找到了多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，這個(gè)類中的其他問題也能找到多項(xiàng)式時(shí)間計(jì)算復(fù)雜算法，法，這個(gè)類中的其他問題也能找到多項(xiàng)式時(shí)間計(jì)算復(fù)雜算法，那么就可以斷定那么就可以斷定P=NPP=NP。 即如果確屬于這個(gè)類中的某個(gè)問題被證明不存在多項(xiàng)式時(shí)間即如果確屬于這個(gè)類中的某個(gè)問題被證明不存在多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，那么，就等于證明了計(jì)算復(fù)雜性算法，那么，就等于證明了PNPPNP。通常，將這類。通常，將這類問題稱為問題稱為NPNP完全問題。完全問題。 19821982年，庫(kù)克因其在計(jì)算復(fù)

40、雜性理論方面（主要是在年，庫(kù)克因其在計(jì)算復(fù)雜性理論方面（主要是在NPNP完完全性理論方面）的奠基性工作而榮獲全性理論方面）的奠基性工作而榮獲ACMACM圖靈獎(jiǎng)。圖靈獎(jiǎng)。 4哲學(xué)家共餐問題 對(duì)哲學(xué)家共餐問對(duì)哲學(xué)家共餐問題可以作這樣的描述題可以作這樣的描述( (如圖如圖5 5所示所示) )：5 5個(gè)哲個(gè)哲學(xué)家圍坐在一張圓桌學(xué)家圍坐在一張圓桌旁，每個(gè)人的面前擺旁，每個(gè)人的面前擺有一碗面條，碗的兩有一碗面條，碗的兩旁各擺有一只筷子。旁各擺有一只筷子。 圖圖5 5哲學(xué)家共餐餐桌示意圖哲學(xué)家共餐餐桌示意圖 假設(shè)哲學(xué)家的生活除了吃飯就是思考問題，而吃飯的假設(shè)哲學(xué)家的生活除了吃飯就是思考問題，而吃飯的時(shí)候需要

41、左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐。時(shí)候需要左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐。吃完后又將筷子放回原處，繼續(xù)思考問題。那么，一個(gè)哲學(xué)吃完后又將筷子放回原處，繼續(xù)思考問題。那么，一個(gè)哲學(xué)家的生活進(jìn)程可表示為：家的生活進(jìn)程可表示為： （1 1）思考問題；）思考問題； （2 2）餓了停止思考，左手拿一只筷子（拿不到就等）；）餓了停止思考，左手拿一只筷子（拿不到就等）； （3 3）右手拿一只筷子（拿不到就等）右手拿一只筷子（拿不到就等） ； （4 4）進(jìn)餐；圖）進(jìn)餐；圖5 5哲學(xué)家共餐餐桌示意圖哲學(xué)家共餐餐桌示意圖 （5 5）放右手筷子；）放右手筷子； （6 6）放左手筷子；）放左

42、手筷子； （7 7）重新回到思考問題狀態(tài)（）重新回到思考問題狀態(tài)（1 1）。）。 問題是：如何協(xié)調(diào)問題是：如何協(xié)調(diào)5 5個(gè)哲學(xué)家的生活進(jìn)程，使得每一個(gè)個(gè)哲學(xué)家的生活進(jìn)程，使得每一個(gè)哲學(xué)家最終都可以進(jìn)餐。哲學(xué)家最終都可以進(jìn)餐。 考慮下面的兩種情況：考慮下面的兩種情況：（1 1）按哲學(xué)家的活動(dòng)進(jìn)程，當(dāng)所有的哲學(xué)家都同時(shí)拿起左）按哲學(xué)家的活動(dòng)進(jìn)程，當(dāng)所有的哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有的哲學(xué)家都將拿不到右手的筷子，并手筷子時(shí)，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無(wú)法進(jìn)餐，最終餓死。處于等待狀態(tài)，那么哲學(xué)家都將無(wú)法進(jìn)餐，最終餓死。（2 2）將哲學(xué)家的活動(dòng)進(jìn)程修改一下，

43、變?yōu)楫?dāng)右手的筷子拿）將哲學(xué)家的活動(dòng)進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時(shí)，就放下左手的筷子，這種情況是不是就沒有問不到時(shí)，就放下左手的筷子，這種情況是不是就沒有問題？不一定，因?yàn)榭赡茉谝粋€(gè)瞬間，所有的哲學(xué)家都同題？不一定，因?yàn)榭赡茉谝粋€(gè)瞬間，所有的哲學(xué)家都同時(shí)拿起左手的筷子，則自然拿不到右手的筷子，于是都時(shí)拿起左手的筷子，則自然拿不到右手的筷子，于是都同時(shí)放下左手的筷子，等一會(huì)，又同時(shí)拿起左手的筷子，同時(shí)放下左手的筷子，等一會(huì)，又同時(shí)拿起左手的筷子，如此這樣永遠(yuǎn)重復(fù)下去，則所有的哲學(xué)家一樣都吃不到如此這樣永遠(yuǎn)重復(fù)下去，則所有的哲學(xué)家一樣都吃不到面條。面條。 以上兩個(gè)方面的問題，其實(shí)反映的是程序

44、并發(fā)執(zhí)行以上兩個(gè)方面的問題，其實(shí)反映的是程序并發(fā)執(zhí)行時(shí)進(jìn)程同步的兩個(gè)問題，一個(gè)是死鎖（時(shí)進(jìn)程同步的兩個(gè)問題，一個(gè)是死鎖（DeadlockDeadlock），另），另一個(gè)是饑餓（一個(gè)是饑餓（StarvationStarvation）。）。 哲學(xué)家共餐問題實(shí)際上反映了計(jì)算機(jī)程序設(shè)計(jì)中多哲學(xué)家共餐問題實(shí)際上反映了計(jì)算機(jī)程序設(shè)計(jì)中多進(jìn)程共享單個(gè)處理機(jī)資源時(shí)的并發(fā)控制問題。要防止這進(jìn)程共享單個(gè)處理機(jī)資源時(shí)的并發(fā)控制問題。要防止這種情況發(fā)生，就必須建立一種機(jī)制，既要讓每一個(gè)哲學(xué)種情況發(fā)生，就必須建立一種機(jī)制，既要讓每一個(gè)哲學(xué)家都能吃到面條，又不能讓任何一個(gè)哲學(xué)家始終拿著一家都能吃到面條，又不能讓任何一個(gè)哲

45、學(xué)家始終拿著一根筷子不放。采用并發(fā)程序語(yǔ)言、根筷子不放。采用并發(fā)程序語(yǔ)言、PetriPetri網(wǎng)、網(wǎng)、CSPCSP等工具，等工具，都能很容易地解決這個(gè)問題。都能很容易地解決這個(gè)問題。 與程序并發(fā)執(zhí)行時(shí)進(jìn)程同步有關(guān)的經(jīng)典問題還有：與程序并發(fā)執(zhí)行時(shí)進(jìn)程同步有關(guān)的經(jīng)典問題還有：讀者寫者問題（讀者寫者問題（ReaderReaderWriter ProblemWriter Problem）、理發(fā)師睡）、理發(fā)師睡眠問題（眠問題（Sleeping Barber ProblemSleeping Barber Problem）等。）等。 5旅行商問題 旅行商問題（旅行商問題（Traveling Salesman

46、 ProblemTraveling Salesman Problem，簡(jiǎn)稱，簡(jiǎn)稱TSPTSP）是威廉）是威廉哈密爾頓（哈密爾頓（W.R.HamiltonW.R.Hamilton）爵士和英國(guó)數(shù)學(xué)）爵士和英國(guó)數(shù)學(xué)家克克曼（家克克曼（T.P.KirkmanT.P.Kirkman）于）于1919世紀(jì)初提出的一個(gè)數(shù)學(xué)問世紀(jì)初提出的一個(gè)數(shù)學(xué)問題。這是一個(gè)典型的題。這是一個(gè)典型的NPNP完全性問題。其大意是：有若干個(gè)完全性問題。其大意是：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且只能在每個(gè)城行商從某城市出

47、發(fā)，必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線，使其旅行的費(fèi)用最少。條最短的路線，使其旅行的費(fèi)用最少。 人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原始的一種方法是：列出每一條可供選擇的路線（即始的一種方法是：列出每一條可供選擇的路線（即對(duì)給定的城市進(jìn)行排列組合），計(jì)算出每條路線的對(duì)給定的城市進(jìn)行排列組合），計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的給定的4 4個(gè)城市分別為個(gè)城市分別為

48、A A、B B、C C和和D D，各城市之間的，各城市之間的距離為已知數(shù)，如圖距離為已知數(shù)，如圖6 6、圖、圖7 7所示。從圖中可以看到，所示。從圖中可以看到，可供選擇的路線共有可供選擇的路線共有6 6條，從中很快可以選出一條條，從中很快可以選出一條總距離最短的路線。總距離最短的路線。ABCD256424圖圖6 6城市交通圖城市交通圖A265BCD244442BDCCBD224444ACCBDBD522665圖圖7 7組合路徑圖組合路徑圖 設(shè)城市數(shù)目為設(shè)城市數(shù)目為n n時(shí)，那么組合路徑數(shù)則為（時(shí)，那么組合路徑數(shù)則為（n-1n-1）！。）！。很顯然，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不很顯然

49、，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)急劇增長(zhǎng)，以至達(dá)到無(wú)法計(jì)算的地步，這就是所謂的級(jí)急劇增長(zhǎng)，以至達(dá)到無(wú)法計(jì)算的地步，這就是所謂的“組合爆炸問題組合爆炸問題”。假設(shè)現(xiàn)在城市的數(shù)目增為。假設(shè)現(xiàn)在城市的數(shù)目增為2020個(gè)，組個(gè)，組合路徑數(shù)則為（合路徑數(shù)則為（20-120-1）！）！1.2161.21610171017，如此龐大的組，如此龐大的組合數(shù)目，若計(jì)算機(jī)以每秒檢索合數(shù)目，若計(jì)算機(jī)以每秒檢索10001000萬(wàn)條路線的速度計(jì)算，萬(wàn)條路線的速度計(jì)算，也需要花上也需要花上386386年的時(shí)間。年的

50、時(shí)間。 6圖靈測(cè)試問題 在計(jì)算機(jī)學(xué)科誕生后，為解決人工智能中一些激烈爭(zhēng)在計(jì)算機(jī)學(xué)科誕生后，為解決人工智能中一些激烈爭(zhēng)論的問題，圖靈和西爾勒又分別提出了能反映人工智能論的問題，圖靈和西爾勒又分別提出了能反映人工智能本質(zhì)特征的兩個(gè)著名的哲學(xué)問題，即本質(zhì)特征的兩個(gè)著名的哲學(xué)問題，即“圖靈測(cè)試圖靈測(cè)試”和西和西爾勒的爾勒的“中文屋子中文屋子”，沿著圖靈等人對(duì)，沿著圖靈等人對(duì)“智能智能”的理解，的理解，人們?cè)谌斯ぶ悄茴I(lǐng)域取得了長(zhǎng)足的進(jìn)展，其中人們?cè)谌斯ぶ悄茴I(lǐng)域取得了長(zhǎng)足的進(jìn)展，其中“深藍(lán)深藍(lán)（Deep BlueDeep Blue）”戰(zhàn)勝國(guó)際象棋大師卡斯帕羅夫戰(zhàn)勝國(guó)際象棋大師卡斯帕羅夫（G.Kasparo

51、vG.Kasparov）就是一個(gè)很好的例證。）就是一個(gè)很好的例證。 圖靈于圖靈于19501950年在英國(guó)年在英國(guó) Mind Mind雜志上發(fā)表了雜志上發(fā)表了Computing Machinery and IntelligenceComputing Machinery and Intelligence一文，文一文，文中提出了中提出了“機(jī)器能思維嗎？機(jī)器能思維嗎？”這樣一個(gè)問題，并給出了這樣一個(gè)問題，并給出了一個(gè)被后人稱之為一個(gè)被后人稱之為“圖靈測(cè)試（圖靈測(cè)試（Turing TestTuring Test）”的模仿的模仿游戲。游戲。 這個(gè)游戲由這個(gè)游戲由3 3個(gè)人來(lái)完成：一個(gè)男人（個(gè)人來(lái)完成：一個(gè)

52、男人（A A），一個(gè)女），一個(gè)女人（人（B B），一個(gè)性別不限的提問者（），一個(gè)性別不限的提問者（C C）。提問者（）。提問者（C C）呆在與其他兩個(gè)游戲者相隔離的房間里。游戲的目標(biāo)是呆在與其他兩個(gè)游戲者相隔離的房間里。游戲的目標(biāo)是讓提問者通過對(duì)其他兩人的提問來(lái)鑒別其中哪個(gè)是男人，讓提問者通過對(duì)其他兩人的提問來(lái)鑒別其中哪個(gè)是男人，哪個(gè)是女人。為了避免提問者通過他們的聲音、語(yǔ)調(diào)輕哪個(gè)是女人。為了避免提問者通過他們的聲音、語(yǔ)調(diào)輕易地作出判斷，最好是在提問者和兩游戲者之間通過一易地作出判斷，最好是在提問者和兩游戲者之間通過一臺(tái)電傳打字機(jī)來(lái)進(jìn)行溝通。提問者只被告知兩個(gè)人的代臺(tái)電傳打字機(jī)來(lái)進(jìn)行溝通。提問

53、者只被告知兩個(gè)人的代號(hào)為號(hào)為X X和和Y Y，游戲的最后他要作出，游戲的最后他要作出“X X是是A A，Y Y是是B”B”或或“X X是是B B，Y Y是是A”A”的判斷。的判斷。 現(xiàn)在，把上面這個(gè)游戲中的男人（現(xiàn)在，把上面這個(gè)游戲中的男人（A A）換成一部機(jī)器來(lái)）換成一部機(jī)器來(lái)扮演，如果提問者在與機(jī)器、女人的游戲中作出的錯(cuò)扮演，如果提問者在與機(jī)器、女人的游戲中作出的錯(cuò)誤判斷與在男人、女人之間的游戲中作出錯(cuò)誤判斷的誤判斷與在男人、女人之間的游戲中作出錯(cuò)誤判斷的次數(shù)是相同的，那么，就可以判定這部機(jī)器是能夠思次數(shù)是相同的，那么，就可以判定這部機(jī)器是能夠思維的。維的。 圖靈關(guān)于圖靈關(guān)于“圖靈測(cè)試圖靈

54、測(cè)試”的論文發(fā)表后引發(fā)了很多的爭(zhēng)的論文發(fā)表后引發(fā)了很多的爭(zhēng)論，以后的學(xué)者在討論機(jī)器思維時(shí)大多都要談到這個(gè)論，以后的學(xué)者在討論機(jī)器思維時(shí)大多都要談到這個(gè)游戲。游戲。 “ “圖靈測(cè)試圖靈測(cè)試”只是從功能的角度來(lái)判定機(jī)器是否能只是從功能的角度來(lái)判定機(jī)器是否能思維，也就是從行為主義角度來(lái)對(duì)思維，也就是從行為主義角度來(lái)對(duì)“機(jī)器思維機(jī)器思維”進(jìn)進(jìn)行定義。盡管圖靈對(duì)行定義。盡管圖靈對(duì)“機(jī)器思維機(jī)器思維”的定義是不夠嚴(yán)的定義是不夠嚴(yán)謹(jǐn)?shù)?，但他關(guān)于謹(jǐn)?shù)?，但他關(guān)于“機(jī)器思維機(jī)器思維”定義的開創(chuàng)性工作對(duì)定義的開創(chuàng)性工作對(duì)后人的研究具有重要意義，因此，一些學(xué)者認(rèn)為，后人的研究具有重要意義，因此，一些學(xué)者認(rèn)為，圖靈發(fā)表

55、的關(guān)于圖靈發(fā)表的關(guān)于“圖靈測(cè)試圖靈測(cè)試”的論文標(biāo)志著現(xiàn)代機(jī)的論文標(biāo)志著現(xiàn)代機(jī)器思維問題討論的開始。器思維問題討論的開始。 根據(jù)圖靈的預(yù)測(cè)，到根據(jù)圖靈的預(yù)測(cè)，到20002000年，此類機(jī)器能通過測(cè)年，此類機(jī)器能通過測(cè)試?，F(xiàn)在，在某些特定的領(lǐng)域，如博弈領(lǐng)域，試?，F(xiàn)在，在某些特定的領(lǐng)域，如博弈領(lǐng)域，“圖圖靈測(cè)試靈測(cè)試”已取得了成功，已取得了成功，19971997年，年，IBMIBM公司研制的計(jì)公司研制的計(jì)算機(jī)算機(jī)“深藍(lán)深藍(lán)”就戰(zhàn)勝了國(guó)際象棋冠軍卡斯帕羅夫。就戰(zhàn)勝了國(guó)際象棋冠軍卡斯帕羅夫。 在未來(lái)，如果我們能像圖靈揭示計(jì)算本質(zhì)那樣揭示在未來(lái)，如果我們能像圖靈揭示計(jì)算本質(zhì)那樣揭示人類思維的本質(zhì)，即人類思

56、維的本質(zhì)，即“能行能行”思維，那么制造真正思思維，那么制造真正思維機(jī)器的日子也就不長(zhǎng)了?？上б獙?duì)人類思維的本質(zhì)維機(jī)器的日子也就不長(zhǎng)了?？上б獙?duì)人類思維的本質(zhì)進(jìn)行描述，還是相當(dāng)遙遠(yuǎn)的事情。進(jìn)行描述，還是相當(dāng)遙遠(yuǎn)的事情。 7搏弈問題 博弈問題屬于人工智能中一個(gè)重要的研究領(lǐng)域。從狹博弈問題屬于人工智能中一個(gè)重要的研究領(lǐng)域。從狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲；從廣義上講，博弈就是對(duì)策或斗智。贏性質(zhì)的游戲；從廣義上講，博弈就是對(duì)策或斗智。計(jì)算機(jī)中的博弈問題，一直是人工智能領(lǐng)域研究的重計(jì)算機(jī)中的博弈問題，一直是人工智能領(lǐng)域研究的重點(diǎn)

57、內(nèi)容之一。點(diǎn)內(nèi)容之一。 1913 1913年，數(shù)學(xué)家策墨洛（年，數(shù)學(xué)家策墨洛（E.ZermeloE.Zermelo）在第五屆國(guó)）在第五屆國(guó)際數(shù)學(xué)會(huì)議上發(fā)表了際數(shù)學(xué)會(huì)議上發(fā)表了關(guān)于集合論在象棋博弈理論關(guān)于集合論在象棋博弈理論中的應(yīng)用中的應(yīng)用（On an Application of Set Theory On an Application of Set Theory to Game of Chessto Game of Chess）的著名論文，第一次把數(shù)學(xué)和）的著名論文，第一次把數(shù)學(xué)和象棋聯(lián)系起來(lái)，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個(gè)新的理象棋聯(lián)系起來(lái)，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個(gè)新的理論，即博弈論。論，即博弈論。 19501950年，年，“信息論信息論”創(chuàng)始人香農(nóng)（創(chuàng)始人香農(nóng)（A.ShannonA.Shannon）發(fā)）發(fā)表了表了國(guó)際象棋與機(jī)器國(guó)際象棋與機(jī)器（A ChessA ChessPlaying Playing MachineMachine）一文，并闡述了用計(jì)算機(jī)編制下棋程序的）一文，并闡述了用計(jì)算機(jī)編制下棋程序的可能性。可能性。 1956 1956年夏天，由麥卡錫（年夏天，由麥卡錫（J.McCarthyJ.McCarthy）和香農(nóng)等）和香農(nóng)等人共同發(fā)起的，在美國(guó)達(dá)特茅斯（人共同發(fā)起的，在美國(guó)達(dá)特茅斯（DartmouthDartmouth）大學(xué)舉）大學(xué)舉行的夏季學(xué)術(shù)討