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

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