計算機領(lǐng)域典型問題.ppt

計算機領(lǐng)域典型問題,在人類社會的發(fā)展過程中，人們提出過許多具有深遠意義的科學(xué)問題，其中對計算機學(xué)科一些分支領(lǐng)域的形成和發(fā)展起了重要的作用。另外，在計算機學(xué)科的發(fā)展過程中，為了便于對計算機科學(xué)中有關(guān)問題和概念的本質(zhì)的理解，人們還給出了不少反映該學(xué)科某一方面本質(zhì)特征的典型實例，在這里一并歸于計算機學(xué)科的典型問題。計算機學(xué)科典型問題的提出及研究，不僅有助于我們深刻地理解計算機學(xué)科，而且還對學(xué)科的發(fā)展有著十分重要的推動作用。,下面分別對圖論中有代表性的哥尼斯堡七橋問題，算法與算法復(fù)雜性領(lǐng)域中有代表性的漢諾（Hanoi）塔問題，算法復(fù)雜性中的難解性問題，證比求易算法，旅行商問題與組合爆炸問題，哲學(xué)家共餐問題,圖靈測試問題，博弈問題等問題及其相關(guān)內(nèi)容進行分析。,補充知識計算機領(lǐng)域典型問題,1歌尼斯堡七橋問題與哈密爾頓回路問題2漢諾塔問題3算法復(fù)雜性中的難解性問題4哲學(xué)家共餐問題5旅行商問題6圖靈測試問題7搏弈問題,1歌尼斯堡七橋問題與哈密爾頓回路問題,18世紀中葉，當時東普魯士有一座哥尼斯堡（Konigsberg）城，城中有一條貫穿全市的普雷格爾（Pregol）河，河中央有座小島，叫奈佛夫（Kneiphof）島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有7座橋?qū)?個城區(qū)相連起來。,圖1哥尼斯堡七橋地理位置示意圖,當時該城市的人們熱衷一個難題：一個人怎樣不重復(fù)地走完七橋，最后回到出發(fā)地點？即尋找走遍這7座橋，且只許走過每座橋一次，最后又回到原出發(fā)點的路徑。試驗者都沒有解決這個難題。1736年，瑞士數(shù)學(xué)家列昂納德歐拉（L.Euler）發(fā)表圖論的首篇論文，論證了該問題無解，即從一點出發(fā)不重復(fù)地走遍七橋，最后又回到原來出發(fā)點是不可能的。他論證所用的圖為圖2所示。后人為了紀念數(shù)學(xué)家歐拉，將這個難題稱為“哥尼斯堡七橋問題”。,圖2哥尼斯堡七橋問題示意圖,為了解決哥尼斯堡七橋問題，歐拉用4個字母A、B、C、D代表4個城區(qū)，并用7條線表示7座橋，如圖2所示。在圖中，只有4個點和7條線，這樣做是基于該問題本質(zhì)的考慮，抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西（如橋的長度等），從而將哥尼斯堡七橋問題抽象成為一個數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。歐拉在論文中論證了這樣的回路是不存在的，后來，人們把有這樣回路的圖稱為歐拉圖。,將其有經(jīng)過所有邊的簡單生成回路的圖稱為歐拉圖歐拉不僅給出了哥尼斯堡七橋問題的證明，還將問題進行了一般化處理，即對給定的任意一個河道圖與任意多座橋，判定可能不可能每座橋恰好走過一次，并用數(shù)學(xué)方法給出了3條判定規(guī)則：,（1）如果通奇數(shù)座橋的地方不止兩個，滿足要求的路線是找不到的；（2）如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一出發(fā)，找到所要求的路線；（3）如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路線都能實現(xiàn)。,歐拉的論文為圖論的形成奠定了基礎(chǔ)。今天，圖論已廣泛地應(yīng)用于計算機科學(xué)、運籌學(xué)、信息論、控制論等科學(xué)之中，并已成為我們對現(xiàn)實問題進行抽象的一個強有力的數(shù)學(xué)工具。隨著計算機科學(xué)的發(fā)展，圖論在計算機科學(xué)中的作用越來越大，同時，圖論本身也得到了充分的發(fā)展。,在圖論中除了歐拉回路以外，還有一個著名的“哈密爾頓回路問題”。十九世紀愛爾蘭數(shù)學(xué)家哈密爾頓(Hamilton)發(fā)明了一種叫做周游世界的數(shù)學(xué)游戲。它的玩法是：給你一個正十二面體，它有二十個頂點，把每個頂點看做一個城市，把正十二面體的三十條棱看成連接這些城市的路。請你找一條從某城市出發(fā)，經(jīng)過每個城市恰好一次，并且最后回到出發(fā)點的路線。我們把正十二面體投影到平面上，在圖3中標出了一種走法，即從城市1出發(fā)，經(jīng)過2，3，20，最后回到1。,“哈密爾頓回路問題”與“歐拉回路問題”看上去十分相似，然而又是完全不同的兩個問題?！肮軤栴D回路問題”是訪問每個結(jié)點一次，而“歐拉回路問題”是訪問每條邊一次。對圖G是否存在“歐拉回路”前面已給出充分必要條件，而對圖G是否存在“哈密爾頓回路”至今仍未找到滿足該問題的充分必要條件。,2漢諾塔問題,傳說在古代印度的貝拿勒斯神廟里安放了一塊黃銅座，座上豎有三根寶石柱子。在第一根寶石柱上，按照從小到大、自上而下的順序放有64個直徑大小不一的金盤子，形成一座金塔，如圖44所示，即所謂的漢諾塔（又稱梵天塔）。天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，即將整個塔遷移，同時定下3條規(guī)則：,（1）每次只能移動一個盤子；（2）盤子只能在三根柱子上來回移動，不能放在他處；（3）在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。圖4漢諾塔問題示意圖64個盤子63個盤子據(jù)說當這64個盤子全部移到第三根柱子上后，世界末日就要到了。這就是著名的漢諾塔塔問題。,圖4漢諾塔問題示意圖,用計算機求解一個實際問題，首先要從這個實際問題中抽象出一個數(shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法，最后根據(jù)算法編寫程序，經(jīng)過調(diào)試和運行，從而完成該問題的求解。從實際問題抽象出一個數(shù)學(xué)模型的實質(zhì)，其實就是要用數(shù)學(xué)的方法抽取問題主要的、本質(zhì)的內(nèi)容，最終實現(xiàn)對該問題的正確認識。,漢諾塔問題是一個典型的用遞歸方法來解決的問題。遞歸是計算機學(xué)科中的一個重要概念。所謂遞歸，就是將一個較大的問題歸約為一個或多個子問題的求解方法。而這些子問題比原問題簡單，且在結(jié)構(gòu)上與原問題相同。,根據(jù)遞歸方法，我們可以將64個盤子的漢諾塔問題轉(zhuǎn)化為求解63個盤子的漢諾塔問題，如果63個盤子的漢諾塔問題能夠解決，則可以將63個盤子先移動到第二個柱子上，再將最后一個盤子直接移動到第三個柱子上，最后又一次將63個盤子從第二個柱子移動到第三個柱子上。,如圖4所示，則可以解決64個盤子的漢諾塔問題。依此類推，63個盤子的漢諾塔求解問題可以轉(zhuǎn)化為62個盤子的漢諾塔求解問題，62個盤子的漢諾塔求解問題又可以轉(zhuǎn)化為61個盤子的漢諾塔求解問題，直到1個盤子的漢諾塔求解問題。再由1個盤子的漢諾塔的解求出2個盤子的漢諾塔，直到解出64個盤子的漢諾塔問題。,按照上面的算法，n個盤子的漢諾塔問題需要移動的盤子數(shù)是n-1個盤子的漢諾塔問題需要移動的盤子數(shù)的2倍加1。于是h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1=2nh(0)+2n-1+22+2+1=2n-1+22+2+1=2n-1,因此，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為：264-1=18446744073709551615如果每秒移動一次，一年有31536000秒，則僧侶們一刻不停地來回搬動，也需要花費大約5849億年的時間。假定計算機以每秒1000萬個盤子的速度進行搬遷，則需要花費大約58490年的時間。,3算法復(fù)雜性中的難解性問題,算法分析是計算機科學(xué)的一項主要工作。為了進行算法比較，我們必須給出算法效率的某種衡量標準。假設(shè)M是一種算法，并設(shè)n為輸入數(shù)據(jù)的規(guī)模。實施M所占用的時間和空間是衡量該算法效率的兩個主要指標。時間由“操作”次數(shù)衡量。比如，對于排序和查找，我們對比較次數(shù)計數(shù)?？臻g由實施該算法所需的最大內(nèi)存來衡量。,算法M的復(fù)雜性是一個函數(shù)(n)，它對于輸人數(shù)據(jù)的規(guī)模n給出運行該算法所需時間與所需存儲空間。執(zhí)行一個算法所需存儲空間通常就是數(shù)據(jù)規(guī)模的倍數(shù)。因此，除非特殊情況，“復(fù)雜性”將指運行算法的時間。,對于時間復(fù)雜性函數(shù)(n)。它通常不僅僅與輸入數(shù)據(jù)的規(guī)模有關(guān)，還與特定的數(shù)據(jù)有關(guān)。例如，在一篇英文短文中查找第一次出現(xiàn)的3個字母的單詞W。那么，如果W為定冠詞“the”，則W很可能在短文的開頭部分出現(xiàn)，于是(n)值將會比較小；如果W是單詞“axe，”，則W甚至可能不會在短文中出現(xiàn)，所以(n)可能會很大。,因此，考慮對于適當?shù)那闆r，求出復(fù)雜性函數(shù)(n)。在復(fù)雜性理論中研究得最多的兩種情況是：(1)最壞情況對于任何可能的輸入，(n)的最大值。(2)平均情況(n)的期望值。,假定M是一個算法，并設(shè)n為輸入數(shù)據(jù)的大小。顯然M的復(fù)雜性(n)隨著n的增大而增大。通常我們需要考察的是(n)的增長率，這常常由(n)與某標準函數(shù)相比較而得，例如log2nn，nlog2n，n2，n3，2n等等，都可被用作為標準函數(shù)，這些函數(shù)是按其增長率列出的：對數(shù)函數(shù)log2n增長最慢，指數(shù)函數(shù)2n增長最快，而多項式函數(shù)nc的增長率隨其指數(shù)c的增大而變快。,將復(fù)雜性函數(shù)與一個標準函數(shù)相比較的一種方法是利用“大O”記號，我們給出它的定義：設(shè)(x)與g(x)為定義于R或R的子集上的任意兩個函數(shù)。我們說“(x)與g(x)同階”，記作(x)O(g(g)。,如果存在實數(shù)k和正常數(shù)C使得對于所有的xk有|(x)|C|g(x)|。如n2+n+1=O(n2)，該表達式表示，當n足夠大時表達式左邊約等于n2。常見的大O表示形式有：O(1)稱為常數(shù)級；O(logn)稱為對數(shù)級；O(n)稱為線性級；,O(nc)稱為多項式級；O(cn)稱為指數(shù)級；O(n!)稱為階乘級。用以上表示方法，在漢諾塔問題中，需要移動的盤子次數(shù)為h(n)=2n-1，則該問題的算法時間復(fù)雜度表示為O(2n)。,一個問題求解算法的時間復(fù)雜度大于多項式（如指數(shù)函數(shù)）時，算法的執(zhí)行時間將隨n的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，于是在計算復(fù)雜性中，將這一類問題稱為難解性問題。為了更好地理解計算及其復(fù)雜性的有關(guān)概念，我國學(xué)者洪加威曾經(jīng)講了一個被人稱為“證比求易算法”的童話，用來幫助讀者理解計算復(fù)雜性的有關(guān)概念，具體內(nèi)容如下。,很久以前，有一個年輕的國王，名叫艾述。他酷愛數(shù)學(xué)，聘請了當時最有名的數(shù)學(xué)家孔喚石當宰相。鄰國有一位聰明美麗的公主，名字叫秋碧貞楠。艾述國王愛上了這位鄰國公主，便親自登門求婚。公主說：“你如果向我求婚，請你先求出48770428433377171的一個真因子，一天之內(nèi)交卷?！卑雎犃T，心中暗喜，心想：我從2開始，一個一個地試，看看能不能除盡這個數(shù)，還怕找不到這個真因子嗎？,艾述國王十分精于計算，他一秒鐘就算完一個數(shù)?？墒?，他從早到晚，共算了三萬多個數(shù)，最終還是沒有結(jié)果。國王向公主求情，公主將答案相告：223092827是它的一個真因子。國王很快就驗證了這個數(shù)確能除盡48770428433377171。,公主說：“我再給你一次機會，如果還求不出，將來你只好做我的證婚人了”。國王立即回國，召見宰相孔喚石，大數(shù)學(xué)家在仔細地思考后認為這個數(shù)為17位，如果這個數(shù)可以分成兩個真因子的乘積，則最小的一個真因子不會超過9位。于是他給國王出了一個主意：按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去，等公主給出數(shù)目后，立即將它們通報全國，讓每個老百姓用自己的編號去除這個數(shù)，除盡了立即上報，賞黃金萬兩。,于是，國王發(fā)動全國上下的民眾，再度求婚，終于取得成功。在“證比求易算法”的故事中，國王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時間方面，后來由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們認為順序算法解決不了的問題完全可以用并行算法來解決，甚至?xí)耄⑿杏嬎銠C系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實這是一種誤解。,當將一個問題分解到多個處理器上解決時，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計算機系統(tǒng)的加速能力。下面，用阿達爾（G.Amdahl）定律來說明這個問題。,設(shè)f為求解某個問題的計算中存在的必須串行執(zhí)行的操作占整個計算的百分比，p為處理器的數(shù)目，Sp為并行計算機系統(tǒng)最大的加速能力（單位：倍），則,設(shè)f=1%，p，則Sp=100。這說明即使在并行計算機系統(tǒng)中有無窮多個處理器，解決這個串行執(zhí)行操作僅占全部操作1%的問題，其解題速度與單處理器的計算機相比最多也只能提高一百倍。因此，對難解性問題而言，單純的提高計算機系統(tǒng)的速度是遠遠不夠的，而降低算法復(fù)雜度的數(shù)量級才是最關(guān)鍵的問題。,國王有眾多百姓的幫助，求親成功是自然的事。但是，如果換成是一個貧民百姓的小伙子去求婚，那就困難了。不過，小伙子可以從國王求親取得成功所采用的并行算法中得到一個啟發(fā)，那就是：他可以隨便猜一個數(shù)，然后驗證這個數(shù)。當然，這樣做成功的可能性很小，不過，萬一小伙子運氣好猜著了呢？由于一個數(shù)和它的因子之間存在一些有規(guī)律的聯(lián)系，因此，數(shù)論知識水平較高的人猜中的可能性就大。,我們說，這個小伙子使用的算法叫做非確定性算法。這樣的算法需要有一種假想但實際并不存在的非確定性計算機才能運行，其理論上的計算模型是非確定性圖靈機。,在算法計算復(fù)雜性的研究中，將所有可以在多項式時間內(nèi)求解的問題稱為P類問題，而將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題，由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，確定性算法是非確定性算法的一個特例，因此PNP。,對于大多數(shù)實際問題來說，找到一個解可能很難，檢驗一個解常常比較容易，所以都屬于NP類問題?，F(xiàn)在計算機科學(xué)研究中一個懸而未決的重要問題是P=?NP。到目前為止，已經(jīng)發(fā)現(xiàn)了一批可計算但有相當難度的問題是屬于NP類問題，并且常通過證明一個問題與已知屬于NP類中的某個問題等價，將其歸入NP類問題。,不過，該問題是否屬于P類問題，即是否能找到多項式時間計算復(fù)雜性算法求解該問題，或證明該問題不存在多項式時間計算復(fù)雜性算法求解，至今尚未解決。20世紀70年代初，庫克（S.A.Cook）和卡爾普（R.M.Karp）在P=?NP問題上取得重大進展，指出NP類中有一小類問題具有以下性質(zhì)：迄今為止，這些問題多數(shù)還沒有人找到多項式時間計算復(fù)雜性算法。但是，一旦其中的一個問題找到了多項式時間計算復(fù)雜性算法，這個類中的其他問題也能找到多項式時間計算復(fù)雜算法，那么就可以斷定P=NP。,即如果確屬于這個類中的某個問題被證明不存在多項式時間計算復(fù)雜性算法，那么，就等于證明了PNP。通常，將這類問題稱為NP完全問題。1982年，庫克因其在計算復(fù)雜性理論方面（主要是在NP完全性理論方面）的奠基性工作而榮獲ACM圖靈獎。,4哲學(xué)家共餐問題,對哲學(xué)家共餐問題可以作這樣的描述(如圖5所示)：5個哲學(xué)家圍坐在一張圓桌旁，每個人的面前擺有一碗面條，碗的兩旁各擺有一只筷子。,假設(shè)哲學(xué)家的生活除了吃飯就是思考問題，而吃飯的時候需要左手拿一只筷子，右手拿一只筷子，然后開始進餐。吃完后又將筷子放回原處，繼續(xù)思考問題。那么，一個哲學(xué)家的生活進程可表示為：（1）思考問題；（2）餓了停止思考，左手拿一只筷子（拿不到就等）；（3）右手拿一只筷子（拿不到就等）；,（4）進餐；圖5哲學(xué)家共餐餐桌示意圖（5）放右手筷子；（6）放左手筷子；（7）重新回到思考問題狀態(tài)（1）。問題是：如何協(xié)調(diào)5個哲學(xué)家的生活進程，使得每一個哲學(xué)家最終都可以進餐。,考慮下面的兩種情況：（1）按哲學(xué)家的活動進程，當所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進餐，最終餓死。,（2）將哲學(xué)家的活動進程修改一下，變?yōu)楫斢沂值目曜幽貌坏綍r，就放下左手的筷子，這種情況是不是就沒有問題？不一定，因為可能在一個瞬間，所有的哲學(xué)家都同時拿起左手的筷子，則自然拿不到右手的筷子，于是都同時放下左手的筷子，等一會，又同時拿起左手的筷子，如此這樣永遠重復(fù)下去，則所有的哲學(xué)家一樣都吃不到面條。,以上兩個方面的問題，其實反映的是程序并發(fā)執(zhí)行時進程同步的兩個問題，一個是死鎖（Deadlock），另一個是饑餓（Starvation）。哲學(xué)家共餐問題實際上反映了計算機程序設(shè)計中多進程共享單個處理機資源時的并發(fā)控制問題。要防止這種情況發(fā)生，就必須建立一種機制，既要讓每一個哲學(xué)家都能吃到面條，又不能讓任何一個哲學(xué)家始終拿著一根筷子不放。采用并發(fā)程序語言、Petri網(wǎng)、CSP等工具，都能很容易地解決這個問題。,與程序并發(fā)執(zhí)行時進程同步有關(guān)的經(jīng)典問題還有：讀者寫者問題（ReaderWriterProblem）、理發(fā)師睡眠問題（SleepingBarberProblem）等。,5旅行商問題,旅行商問題（TravelingSalesmanProblem，簡稱TSP）是威廉哈密爾頓（W.R.Hamilton）爵士和英國數(shù)學(xué)家克克曼（T.P.Kirkman）于19世紀初提出的一個數(shù)學(xué)問題。這是一個典型的NP完全性問題。其大意是：有若干個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線，使其旅行的費用最少。,人們在考慮解決這個問題時，一般首先想到的最原始的一種方法是：列出每一條可供選擇的路線（即對給定的城市進行排列組合），計算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個城市分別為A、B、C和D，各城市之間的距離為已知數(shù)，如圖6、圖7所示。從圖中可以看到，可供選擇的路線共有6條，從中很快可以選出一條總距離最短的路線。,設(shè)城市數(shù)目為n時，那么組合路徑數(shù)則為（n-1）！。很顯然，當城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級急劇增長，以至達到無法計算的地步，這就是所謂的“組合爆炸問題”。假設(shè)現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為（20-1）！1.2161017，如此龐大的組合數(shù)目，若計算機以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間。,6圖靈測試問題,在計算機學(xué)科誕生后，為解決人工智能中一些激烈爭論的問題，圖靈和西爾勒又分別提出了能反映人工智能本質(zhì)特征的兩個著名的哲學(xué)問題，即“圖靈測試”和西爾勒的“中文屋子”，沿著圖靈等人對“智能”的理解，人們在人工智能領(lǐng)域取得了長足的進展，其中“深藍（DeepBlue）”戰(zhàn)勝國際象棋大師卡斯帕羅夫（G.Kasparov）就是一個很好的例證。,圖靈于1950年在英國Mind雜志上發(fā)表了ComputingMachineryandIntelligence一文，文中提出了“機器能思維嗎？”這樣一個問題，并給出了一個被后人稱之為“圖靈測試（TuringTest）”的模仿游戲。,這個游戲由3個人來完成：一個男人（A），一個女人（B），一個性別不限的提問者（C）。提問者（C）呆在與其他兩個游戲者相隔離的房間里。游戲的目標是讓提問者通過對其他兩人的提問來鑒別其中哪個是男人，哪個是女人。為了避免提問者通過他們的聲音、語調(diào)輕易地作出判斷，最好是在提問者和兩游戲者之間通過一臺電傳打字機來進行溝通。提問者只被告知兩個人的代號為X和Y，游戲的最后他要作出“X是A，Y是B”或“X是B，Y是A”的判斷。,現(xiàn)在，把上面這個游戲中的男人（A）換成一部機器來扮演，如果提問者在與機器、女人的游戲中作出的錯誤判斷與在男人、女人之間的游戲中作出錯誤判斷的次數(shù)是相同的，那么，就可以判定這部機器是能夠思維的。圖靈關(guān)于“圖靈測試”的論文發(fā)表后引發(fā)了很多的爭論，以后的學(xué)者在討論機器思維時大多都要談到這個游戲。,“圖靈測試”只是從功能的角度來判定機器是否能思維，也就是從行為主義角度來對“機器思維”進行定義。盡管圖靈對“機器思維”的定義是不夠嚴謹?shù)?，但他關(guān)于“機器思維”定義的開創(chuàng)性工作對后人的研究具有重要意義，因此，一些學(xué)者認為，圖靈發(fā)表的關(guān)于“圖靈測試”的論文標志著現(xiàn)代機器思維問題討論的開始。,根據(jù)圖靈的預(yù)測，到2000年，此類機器能通過測試?，F(xiàn)在，在某些特定的領(lǐng)域，如博弈領(lǐng)域，“圖靈測試”已取得了成功，1997年，IBM公司研制的計算機“深藍”就戰(zhàn)勝了國際象棋冠軍卡斯帕羅夫。,在未來，如果我們能像圖靈揭示計算本質(zhì)那樣揭示人類思維的本質(zhì)，即“能行”思維，那么制造真正思維機器的日子也就不長了。可惜要對人類思維的本質(zhì)進行描述，還是相當遙遠的事情。,7搏弈問題,博弈問題屬于人工智能中一個重要的研究領(lǐng)域。從狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲；從廣義上講，博弈就是對策或斗智。計算機中的博弈問題，一直是人工智能領(lǐng)域研究的重點內(nèi)容之一。,1913年，數(shù)學(xué)家策墨洛（E.Zermelo）在第五屆國際數(shù)學(xué)會議上發(fā)表了關(guān)于集合論在象棋博弈理論中的應(yīng)用（OnanApplicationofSetTheorytoGameofChess）的著名論文，第一次把數(shù)學(xué)和象棋聯(lián)系起來，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個新的理論，即博弈論。1950年，“信息論”創(chuàng)始人香農(nóng)（A.Shannon）發(fā)表了國際象棋與機器（AChessPlayingMachine）一文，并闡述了用計算機編制下棋程序的可能性。,1956年夏天，由麥卡錫（J.McCarthy）和香農(nóng)等人共同發(fā)起的，在美國達特茅斯（Dartmouth）大學(xué)舉行的夏季學(xué)術(shù)討論會上，第一次正式使用了“人工智能