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

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

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

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

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

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

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

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

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

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

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

11、正十二面體點的路線。我們把正十二面體投影到平面上，在圖投影到平面上，在圖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 “ “哈密爾頓回路問題哈密爾頓回路問題”與與“歐拉回路問題歐拉回路問題”看上去十分相似，然而又是完全不同的兩個問題。看上去十分相似，然而又是完全不同的兩個問題?！肮軤栴D回路問題哈密爾頓回路問題”是訪問每個結(jié)點一次，而是訪問每個結(jié)點一次，而“歐拉回路問題歐拉回路問題”是訪問每條邊

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

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

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

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

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

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

18、問題。漢諾塔問題。 按照上面的算法，按照上面的算法，n n個盤子的漢諾塔問題需要移動的盤子個盤子的漢諾塔問題需要移動的盤子數(shù)是數(shù)是n-1n-1個盤子的漢諾塔問題需要移動的盤子數(shù)的個盤子的漢諾塔問題需要移動的盤子數(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因此，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為：因此，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為： 264-1=18446744073709551615 264-1=18446744073709551615 如果每秒移動一次，一年有如果每秒移動一次，一年有3153600031536000秒，則僧侶們秒，則僧侶們一刻不停地來回搬動，也需要花費大約一刻不停地來回搬動，也需要花費大約58495849億年的億年的時間。假定計算機(jī)以每秒時間。假定計算機(jī)以每秒10001000萬個盤子的速度進(jìn)行萬個盤子的速度進(jìn)行搬遷，則需要花費大約搬遷，則需要花費大約58

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

21、數(shù)計數(shù)?？臻g由實施該算法所需的最大內(nèi)存來衡量。衡量。 n算法算法M M的復(fù)雜性是一個函數(shù)的復(fù)雜性是一個函數(shù)(n(n) )，它對于輸人數(shù)據(jù)的規(guī)模，它對于輸人數(shù)據(jù)的規(guī)模n n給出運行該算法所需時間與所需存儲空間。執(zhí)行一個算給出運行該算法所需時間與所需存儲空間。執(zhí)行一個算法所需存儲空間通常就是數(shù)據(jù)規(guī)模的倍數(shù)。因此，除非法所需存儲空間通常就是數(shù)據(jù)規(guī)模的倍數(shù)。因此，除非特殊情況，特殊情況，“復(fù)雜性復(fù)雜性”將指運行算法的時間。將指運行算法的時間。 對于時間復(fù)雜性函數(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個字母的單詞個字母的單詞W W。那么，。那么，如果如果W W為定冠詞為定冠詞“the”the”，則，則W W很可能在短文的開頭部分出很可能在短文的開頭部分出現(xiàn)，于是現(xiàn)，于是(n)(n)值將會比較?。蝗绻祵容^??；如果W W是單詞是單詞“axeaxe，”，則則W W甚至可能不會在短文中出現(xiàn)，所以甚至可能不會在短文中出現(xiàn)，所以(n)(n)可能會很大?？赡軙艽?。 因此，考慮對于適當(dāng)?shù)那闆r，求出復(fù)雜性函數(shù)因此，考慮對于適當(dāng)?shù)那闆r，求出復(fù)雜性函數(shù)(n)(n)。在復(fù)雜性理論中研究得最多的兩種情況是：。在復(fù)雜性理論中研究

23、得最多的兩種情況是： (1)(1)最壞情況最壞情況 對于任何可能的輸入，對于任何可能的輸入，(n)(n)的最大值。的最大值。 (2)(2)平均情況平均情況 (n)(n)的期望值。的期望值。 假定假定M M是一個算法，并設(shè)是一個算法，并設(shè)n n為輸入數(shù)據(jù)的大小。顯然為輸入數(shù)據(jù)的大小。顯然M M的復(fù)的復(fù)雜性雜性(n)(n)隨著隨著n n的增大而增大。通常我們需要考察的是的增大而增大。通常我們需要考察的是(n)(n)的增長率，這常常由的增長率，這常常由(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ù)是按其增長等等，都可被用作為標(biāo)準(zhǔn)函數(shù)，這些函數(shù)是按其增長率列出的：對數(shù)函數(shù)率列出的：對數(shù)函數(shù)log2nlog2n增長最慢，指數(shù)函數(shù)增長最慢，指數(shù)函數(shù)2n2n增長最增長最快，而多項式函數(shù)快，而多項式函數(shù)ncnc的增長率隨其指數(shù)的增長率隨其指數(shù)c c的增大而變快。的增大而變快。 將復(fù)雜性函數(shù)與一個標(biāo)準(zhǔn)函數(shù)相比較的一種方法是利將復(fù)雜性函數(shù)與一個標(biāo)準(zhǔn)函數(shù)相比較的一種方法是利用用“大大O”記號，我們給出它的定義：記號，我們給出它的定義： 設(shè)設(shè)(x(x) )與與g(xg(x) )為定義于為定義于R R或或R R的子集上的任意兩個函的子

25、集上的任意兩個函數(shù)。我們說數(shù)。我們說“(x(x) )與與g(xg(x) )同階同階”，記作，記作 (x(x) )O(g(g(g(g)。 如果存在實數(shù)如果存在實數(shù)k k和正常數(shù)和正常數(shù)C C使得對于所有的使得對于所有的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足夠大時表達(dá)式左邊約足夠大時表達(dá)式左邊約等于等于n n2 2。常見的大常見的大O O表示形式有：表示形式有： O(1)(1)稱為常數(shù)級；稱為常數(shù)級； O(logn)(logn)稱為對數(shù)級；稱為對數(shù)級；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐。時候需要左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐。吃完后又將筷子放回原處，繼續(xù)思考問題。那么，一個哲學(xué)吃完后又將筷子放回原處，繼續(xù)思考問題。那么，一個哲學(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個哲學(xué)家的生活進(jìn)程，使得每一個個哲學(xué)家的生活進(jìn)程，使得每一個哲學(xué)家最終都可以進(jìn)餐。哲學(xué)家最終都可以進(jìn)餐。 考慮下面的兩種情況：考慮下面的兩種情況：（1 1）按哲學(xué)家的活動進(jìn)程，當(dāng)所有的哲學(xué)家都同時拿起左）按哲學(xué)家的活動進(jìn)程，當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進(jìn)餐，最終餓死。處于等待狀態(tài)，那么哲學(xué)家都將無法進(jìn)餐，最終餓死。（2 2）將哲學(xué)家的活動進(jìn)程修改一下，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57、內(nèi)容之一。點內(nèi)容之一。 1913 1913年，數(shù)學(xué)家策墨洛（年，數(shù)學(xué)家策墨洛（E.ZermeloE.Zermelo）在第五屆國）在第五屆國際數(shù)學(xué)會議上發(fā)表了際數(shù)學(xué)會議上發(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)系起來，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個新的理象棋聯(lián)系起來，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個新的理論，即博弈論。論，即博弈論。 19501950年，年，“信息論信息論”創(chuàng)始人香農(nóng)（創(chuàng)始人香農(nóng)（A.ShannonA.Shannon）發(fā)）發(fā)表了表了國際象棋與機(jī)器國際象棋與機(jī)器（A ChessA ChessPlaying Playing MachineMachine）一文，并闡述了用計算機(jī)編制下棋程序的）一文，并闡述了用計算機(jī)編制下棋程序的可能性。可能性。 1956 1956年夏天，由麥卡錫（年夏天，由麥卡錫（J.McCarthyJ.McCarthy）和香農(nóng)等）和香農(nóng)等人共同發(fā)起的，在美國達(dá)特茅斯（人共同發(fā)起的，在美國達(dá)特茅斯（DartmouthDartmouth）大學(xué)舉）大學(xué)舉行的夏季學(xué)術(shù)討