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

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