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

1、 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)第第8章章 計(jì)算機(jī)領(lǐng)域的典型問題計(jì)算機(jī)領(lǐng)域的典型問題8.1 圖論問題圖論問題 8.2 算法復(fù)雜性問題算法復(fù)雜性問題 8.3 計(jì)算機(jī)智能問題計(jì)算機(jī)智能問題 8.4 并發(fā)控制問題并發(fā)控制問題8.5 本章小結(jié)本章小結(jié) 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.1 圖論問題圖論問題 歌尼斯堡七橋問題歌尼斯堡七橋問題哈密爾頓回路問題哈密爾頓回路問題中國(guó)郵路問題中國(guó)郵路問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題問題描述問題描述一個(gè)人怎樣不重復(fù)地走完七座橋，最后還能回到原一個(gè)人怎樣不重復(fù)地走完七座橋，最后還能回到原出發(fā)地點(diǎn)？出發(fā)地點(diǎn)？ 計(jì)算

2、機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題歐拉對(duì)歐拉對(duì)哥尼斯堡哥尼斯堡七橋問題進(jìn)行了研究七橋問題進(jìn)行了研究1736年，歐拉論證了該問題無(wú)解。年，歐拉論證了該問題無(wú)解。從一點(diǎn)出發(fā)不重復(fù)地走遍從一點(diǎn)出發(fā)不重復(fù)地走遍7座橋，最后又回到原來(lái)出發(fā)點(diǎn)座橋，最后又回到原來(lái)出發(fā)點(diǎn)是不可能的。是不可能的。歐拉對(duì)了問題進(jìn)行了抽象歐拉對(duì)了問題進(jìn)行了抽象 描述：用描述：用4個(gè)字母?jìng)€(gè)字母A、B、 C、D代表代表4個(gè)城區(qū)，并用個(gè)城區(qū)，并用 7條邊表示條邊表示7座橋。座橋。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)歐拉的歐拉的3 3條判定規(guī)則條判定規(guī)則如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路如果通奇

3、數(shù)座橋的地方不止兩個(gè)，滿足要求的路徑是找不到的。徑是找不到的。如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路徑。方之一出發(fā)，找到所要求的路徑。如果沒有一個(gè)地方是通奇數(shù)座橋的，則無(wú)論從哪如果沒有一個(gè)地方是通奇數(shù)座橋的，則無(wú)論從哪里出發(fā)，所要求的路徑都能實(shí)現(xiàn)。里出發(fā)，所要求的路徑都能實(shí)現(xiàn)。8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)歐拉的研究工作奠定了圖論的基礎(chǔ)歐拉的研究工作奠定了圖論的基礎(chǔ)涉及到的后續(xù)課程。涉及到的后續(xù)課程。離散數(shù)學(xué)。離散數(shù)學(xué)。數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)。應(yīng)用領(lǐng)域。應(yīng)用領(lǐng)域。計(jì)算機(jī)網(wǎng)絡(luò)性能分

4、析。計(jì)算機(jī)網(wǎng)絡(luò)性能分析。交通運(yùn)輸網(wǎng)絡(luò)調(diào)度。交通運(yùn)輸網(wǎng)絡(luò)調(diào)度。地下管網(wǎng)配置。地下管網(wǎng)配置。8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題航空網(wǎng)絡(luò) 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.1.2 哈密頓回路問題哈密頓回路問題問題描述（周游世界游戲）問題描述（周游世界游戲）找一條從某個(gè)城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，找一條從某個(gè)城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后回到出發(fā)地的路徑。最后回到出發(fā)地的路徑。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)哈密頓回路哈密頓回路與與歐拉回路歐拉回路的區(qū)別的區(qū)別哈密頓回路問題哈密頓回路問題是訪問每個(gè)頂點(diǎn)一次，而是訪問每個(gè)頂點(diǎn)一次，而歐拉回路歐拉回路問題問題是訪問每條邊一次。是訪問

5、每條邊一次。對(duì)于一個(gè)圖是否存在對(duì)于一個(gè)圖是否存在歐拉回路歐拉回路，已給出充要條件；，已給出充要條件；而對(duì)于一個(gè)圖是否存在而對(duì)于一個(gè)圖是否存在哈密頓回路哈密頓回路至今仍未找到充至今仍未找到充要條件。要條件。8.1.2 哈密頓回路問題哈密頓回路問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)問題描述問題描述一個(gè)郵遞員應(yīng)如何選擇一條路線，使他能夠從郵局出發(fā)，一個(gè)郵遞員應(yīng)如何選擇一條路線，使他能夠從郵局出發(fā)，走遍他負(fù)責(zé)送信的所有街道，最后回到郵局，并且所走走遍他負(fù)責(zé)送信的所有街道，最后回到郵局，并且所走的路程最短。的路程最短。歸結(jié)為圖論問題：給定一個(gè)連通無(wú)向圖，求該圖的一條歸結(jié)為圖論問題：給定一個(gè)連通無(wú)向圖，求

6、該圖的一條經(jīng)過每條邊至少一次的最短回路。經(jīng)過每條邊至少一次的最短回路。對(duì)于歐拉圖，找到一條歐拉回路即可。對(duì)于非歐拉圖，對(duì)于歐拉圖，找到一條歐拉回路即可。對(duì)于非歐拉圖，才是中國(guó)郵路問題的研究重點(diǎn)。才是中國(guó)郵路問題的研究重點(diǎn)。 8.1.3 中國(guó)郵路問題中國(guó)郵路問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2 算法復(fù)雜性問題算法復(fù)雜性問題 漢諾塔問題漢諾塔問題旅行商問題旅行商問題 NP完全問題完全問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.1 漢諾塔問題漢諾塔問題問題描述問題描述將第一根柱子上的將第一根柱子上的64個(gè)盤子借助第二根柱子全部移個(gè)盤子借助第二根柱子全部移到第三根柱子上。到第三根柱子上。64

7、個(gè)盤子63個(gè)盤子 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.1 漢諾塔問題漢諾塔問題移動(dòng)規(guī)則移動(dòng)規(guī)則每次只能移動(dòng)一個(gè)盤子。每次只能移動(dòng)一個(gè)盤子。盤子只能在三根柱子上移動(dòng)，不能放在他處。盤子只能在三根柱子上移動(dòng)，不能放在他處。在移動(dòng)過程中，三根柱子上的盤子必須始終保持在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。大盤在下，小盤在上。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)遞歸思想遞歸思想將一個(gè)較大的問題的求解歸約為一個(gè)或多個(gè)子問題將一個(gè)較大的問題的求解歸約為一個(gè)或多個(gè)子問題的求解。而這些子問題比原問題簡(jiǎn)單，且在結(jié)構(gòu)上的求解。而這些子問題比原問題簡(jiǎn)單，且在結(jié)構(gòu)上與原問題相同。與原問題相同。

8、從前有座山 從前有座山 從前有座山8.2.1 漢諾塔問題漢諾塔問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.1 漢諾塔問題漢諾塔問題用遞歸方法求解用遞歸方法求解移動(dòng)移動(dòng)n個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)是個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)是n-1個(gè)盤個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)的子的漢諾塔問題需要移動(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 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.1 漢諾塔問題漢諾

9、塔問題用遞歸方法求解用遞歸方法求解每次只能移動(dòng)一個(gè)盤子，要完成漢諾塔的搬遷，每次只能移動(dòng)一個(gè)盤子，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為：需要移動(dòng)盤子的次數(shù)為： 264-1=18 446 744 073 709 551 615每秒移動(dòng)一次，需要大約每秒移動(dòng)一次，需要大約5849億年的時(shí)間。億年的時(shí)間。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.2 旅行商問題旅行商問題問題描述問題描述一旅行商從某城市出發(fā)，必須經(jīng)過每個(gè)城市且只能經(jīng)過一次，最后回一旅行商從某城市出發(fā)，必須經(jīng)過每個(gè)城市且只能經(jīng)過一次，最后回到原出發(fā)城市。到原出發(fā)城市。要求找到一條距離最短的路徑（或費(fèi)用最少的路徑）。要求找到一條距離最

10、短的路徑（或費(fèi)用最少的路徑）。原始的解決辦法原始的解決辦法列出每條可能的路徑。列出每條可能的路徑。從中選擇距離最短的路徑。從中選擇距離最短的路徑。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.2 旅行商問題旅行商問題遇到的困難遇到的困難城市個(gè)數(shù)較多時(shí)難以實(shí)現(xiàn)。城市個(gè)數(shù)較多時(shí)難以實(shí)現(xiàn)。組合爆炸問題。組合爆炸問題?？尚械慕鉀Q辦法可行的解決辦法啟發(fā)式算法。啟發(fā)式算法。近似算法。近似算法。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.2.3 NP完全問題完全問題P類問題類問題將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P類問題。類問題。 NP類問題類問題將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證

11、的問題稱為將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題稱為NP類問題。類問題。 NP完全問題完全問題在在NP類問題中，某些問題的復(fù)雜性與整個(gè)類的復(fù)雜性類問題中，某些問題的復(fù)雜性與整個(gè)類的復(fù)雜性有關(guān)，如果這些問題中的任意一個(gè)能在多項(xiàng)式的時(shí)間有關(guān)，如果這些問題中的任意一個(gè)能在多項(xiàng)式的時(shí)間內(nèi)求解，則所有內(nèi)求解，則所有NP類問題都能在多項(xiàng)式時(shí)間內(nèi)求解，類問題都能在多項(xiàng)式時(shí)間內(nèi)求解，這些這些NP類問題稱為類問題稱為NP完全問題。完全問題。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3 計(jì)算機(jī)智能問題計(jì)算機(jī)智能問題 圖靈測(cè)試圖靈測(cè)試西爾勒中文小屋西爾勒中文小屋博弈問題博弈問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.1

12、圖靈測(cè)試圖靈測(cè)試機(jī)器能思維嗎機(jī)器能思維嗎 ？ 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.1 圖靈測(cè)試圖靈測(cè)試圖靈測(cè)試游戲圖靈測(cè)試游戲游戲的參與者游戲的參與者一個(gè)男人、一個(gè)女人和一個(gè)不限性別的提問者。一個(gè)男人、一個(gè)女人和一個(gè)不限性別的提問者。游戲目標(biāo)游戲目標(biāo)提問者通過對(duì)其他兩人的提問，來(lái)鑒別其中的男女。提問者通過對(duì)其他兩人的提問，來(lái)鑒別其中的男女。游戲要求游戲要求提問者呆在與其他兩個(gè)游戲者相隔離的房間里。提問者呆在與其他兩個(gè)游戲者相隔離的房間里。提問者和兩游戲者之間通過電傳打字機(jī)進(jìn)行溝通。提問者和兩游戲者之間通過電傳打字機(jī)進(jìn)行溝通。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.1 圖靈測(cè)試圖靈測(cè)試圖靈

13、測(cè)試游戲圖靈測(cè)試游戲把游戲中的男人換成機(jī)器。把游戲中的男人換成機(jī)器。若提問者在與機(jī)器、女人的游戲中作出的錯(cuò)誤判斷若提問者在與機(jī)器、女人的游戲中作出的錯(cuò)誤判斷與在男人、女人之間的游戲中作出的錯(cuò)誤判斷，其與在男人、女人之間的游戲中作出的錯(cuò)誤判斷，其次數(shù)相同或更多，則判定這部機(jī)器能夠思維。次數(shù)相同或更多，則判定這部機(jī)器能夠思維。根據(jù)圖靈當(dāng)時(shí)的預(yù)測(cè)，到根據(jù)圖靈當(dāng)時(shí)的預(yù)測(cè)，到2000年能有機(jī)器通過這樣年能有機(jī)器通過這樣的測(cè)試。有人認(rèn)為，在的測(cè)試。有人認(rèn)為，在1997年戰(zhàn)勝國(guó)際象棋大師卡年戰(zhàn)勝國(guó)際象棋大師卡斯帕羅夫的斯帕羅夫的深藍(lán)深藍(lán)計(jì)算機(jī)可以看作通過了圖靈測(cè)試。計(jì)算機(jī)可以看作通過了圖靈測(cè)試。 計(jì)算機(jī)導(dǎo)論

14、計(jì)算機(jī)導(dǎo)論(2009)8.3.2 西爾勒中文小屋西爾勒中文小屋問題描述問題描述西爾勒被關(guān)在一個(gè)小屋中，屋子里有序地堆放著足西爾勒被關(guān)在一個(gè)小屋中，屋子里有序地堆放著足夠的中文字符，而他對(duì)中文一竅不通。夠的中文字符，而他對(duì)中文一竅不通。屋外的人遞進(jìn)一串中文字符，同時(shí)還附有一本用英屋外的人遞進(jìn)一串中文字符，同時(shí)還附有一本用英文編寫的處理中文字符的規(guī)則，這些規(guī)則將遞進(jìn)來(lái)文編寫的處理中文字符的規(guī)則，這些規(guī)則將遞進(jìn)來(lái)的字符和小屋中的字符之間的轉(zhuǎn)換作了形式化的規(guī)的字符和小屋中的字符之間的轉(zhuǎn)換作了形式化的規(guī)定。定。西爾勒按照規(guī)則對(duì)這些字符進(jìn)行處理后，將一串新西爾勒按照規(guī)則對(duì)這些字符進(jìn)行處理后，將一串新的中文

15、字符送出屋外。的中文字符送出屋外。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.2 西爾勒中文小屋西爾勒中文小屋問題描述問題描述實(shí)際上，送進(jìn)來(lái)的字符串就是屋外人提出的實(shí)際上，送進(jìn)來(lái)的字符串就是屋外人提出的問題問題，送出去的字符串就是所提出問題的送出去的字符串就是所提出問題的答案答案。但。但西爾勒西爾勒并不清楚自己在做什么？并不清楚自己在做什么？ 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.2 西爾勒中文小屋西爾勒中文小屋西爾勒的觀點(diǎn)西爾勒的觀點(diǎn)形式化的計(jì)算機(jī)僅有語(yǔ)法，沒有語(yǔ)義，只是按規(guī)形式化的計(jì)算機(jī)僅有語(yǔ)法，沒有語(yǔ)義，只是按規(guī)則辦事，并不理解規(guī)則的含義及自己在做什么？則辦事，并不理解規(guī)則的含義及自己在

16、做什么？機(jī)器永遠(yuǎn)也不可能代替人腦。機(jī)器永遠(yuǎn)也不可能代替人腦。圖靈的觀點(diǎn)圖靈的觀點(diǎn)不要求機(jī)器與人腦在內(nèi)部構(gòu)造上一樣，只要與人不要求機(jī)器與人腦在內(nèi)部構(gòu)造上一樣，只要與人腦有相同的功能就認(rèn)為機(jī)器有思維。腦有相同的功能就認(rèn)為機(jī)器有思維。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)人工智能的含義人工智能的含義研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能研究的目標(biāo)人工智能研究的目標(biāo)使機(jī)器能夠勝任一些通常需要人類智能才能完成的復(fù)雜使機(jī)器能夠勝任一些通常需要人類智能才能完成的復(fù)雜工作。

17、工作。 8.3.2 西爾勒中文小屋西爾勒中文小屋 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)人工智能的不同觀點(diǎn)人工智能的不同觀點(diǎn)符號(hào)主義符號(hào)主義：認(rèn)為人的認(rèn)知基元是符號(hào)，認(rèn)為人是一個(gè)物認(rèn)為人的認(rèn)知基元是符號(hào)，認(rèn)為人是一個(gè)物理符號(hào)系統(tǒng)，計(jì)算機(jī)也是一個(gè)物理符號(hào)系統(tǒng)，因而能夠理符號(hào)系統(tǒng)，計(jì)算機(jī)也是一個(gè)物理符號(hào)系統(tǒng)，因而能夠用計(jì)算機(jī)來(lái)模擬人的智能行為。用計(jì)算機(jī)來(lái)模擬人的智能行為。連接主義連接主義：認(rèn)為人的思維基元是神經(jīng)元，而不是符號(hào)處認(rèn)為人的思維基元是神經(jīng)元，而不是符號(hào)處理過程。認(rèn)為人腦不同于電腦，主張人工智能應(yīng)著重于理過程。認(rèn)為人腦不同于電腦，主張人工智能應(yīng)著重于結(jié)構(gòu)模擬。結(jié)構(gòu)模擬。行為主義行為主義：認(rèn)為智能

18、取決于感知和行動(dòng)，提出智能行為認(rèn)為智能取決于感知和行動(dòng)，提出智能行為的的感知?jiǎng)幼鞲兄獎(jiǎng)幼髂Ｊ健ＤＪ健?.3.2 西爾勒中文小屋西爾勒中文小屋 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)人工智能的展望人工智能的展望目前人們對(duì)心理學(xué)和生物學(xué)的認(rèn)識(shí)還很不成熟，對(duì)目前人們對(duì)心理學(xué)和生物學(xué)的認(rèn)識(shí)還很不成熟，對(duì)人腦的結(jié)構(gòu)還沒有真正了解，無(wú)法建立起人腦思維人腦的結(jié)構(gòu)還沒有真正了解，無(wú)法建立起人腦思維完整的數(shù)學(xué)模型。完整的數(shù)學(xué)模型。讓計(jì)算機(jī)具有和人腦完全一樣的智能，不是短期內(nèi)讓計(jì)算機(jī)具有和人腦完全一樣的智能，不是短期內(nèi)能夠?qū)崿F(xiàn)的。能夠?qū)崿F(xiàn)的。在相當(dāng)長(zhǎng)的時(shí)間內(nèi)，只能從不同的側(cè)面、以不同的在相當(dāng)長(zhǎng)的時(shí)間內(nèi)，只能從不同的側(cè)面

19、、以不同的方式讓計(jì)算機(jī)具有某些類似人的智能。方式讓計(jì)算機(jī)具有某些類似人的智能。8.3.2 西爾勒中文小屋西爾勒中文小屋 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.3 博弈問題博弈問題博弈的含義博弈的含義狹義上講，博弈是指下棋、玩撲克牌、擲骰子等狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲。具有輸贏性質(zhì)的游戲。廣義上講，博弈就是對(duì)策或斗智。廣義上講，博弈就是對(duì)策或斗智。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.3.3 博弈問題博弈問題雙人完備博弈雙人完備博弈兩位選手對(duì)壘，輪流走步，其中一方完全知道另兩位選手對(duì)壘，輪流走步，其中一方完全知道另一方已經(jīng)走過的棋步以及未來(lái)可能的棋步。一方已經(jīng)

20、走過的棋步以及未來(lái)可能的棋步。對(duì)弈的結(jié)果要么是一方贏（另一方輸），要么是對(duì)弈的結(jié)果要么是一方贏（另一方輸），要么是和局。和局。對(duì)于任何一種雙人完備博弈，都可以用一個(gè)博弈對(duì)于任何一種雙人完備博弈，都可以用一個(gè)博弈樹來(lái)描述，并通過博弈樹搜索策略尋找最佳解。樹來(lái)描述，并通過博弈樹搜索策略尋找最佳解。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)博弈樹博弈樹博弈樹類似于狀態(tài)圖和問題求解搜索中使用的搜博弈樹類似于狀態(tài)圖和問題求解搜索中使用的搜索樹。索樹。搜索樹上的一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)棋局，樹的分支表搜索樹上的一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)棋局，樹的分支表示棋的走步，根結(jié)點(diǎn)表示棋局的開始，葉結(jié)點(diǎn)表示棋的走步，根結(jié)點(diǎn)表示棋局的開始，葉結(jié)

21、點(diǎn)表示棋局的結(jié)束。示棋局的結(jié)束。博弈樹是非常大的，國(guó)際象棋有博弈樹是非常大的，國(guó)際象棋有10120個(gè)結(jié)點(diǎn)，中個(gè)結(jié)點(diǎn)，中國(guó)象棋來(lái)有國(guó)象棋來(lái)有10160個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。8.3.3 博弈問題博弈問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)中國(guó)象棋博弈樹中國(guó)象棋博弈樹8.3.3 博弈問題博弈問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4 并發(fā)控制問題并發(fā)控制問題 生產(chǎn)者生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題哲學(xué)家共餐問題哲學(xué)家共餐問題 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4.1 生產(chǎn)者生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題問題描述問題描述有有n個(gè)生產(chǎn)者和個(gè)生產(chǎn)者和m個(gè)消費(fèi)者，在生產(chǎn)者和消費(fèi)者個(gè)消費(fèi)者，在生產(chǎn)者和消費(fèi)者之間設(shè)置了一

22、個(gè)能存放之間設(shè)置了一個(gè)能存放k個(gè)產(chǎn)品的貨架。個(gè)產(chǎn)品的貨架。只要貨架未滿，生產(chǎn)者只要貨架未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)品就可以放入生產(chǎn)的產(chǎn)品就可以放入貨架，每次放入一個(gè)產(chǎn)品；貨架，每次放入一個(gè)產(chǎn)品；只要貨架非空，消費(fèi)者只要貨架非空，消費(fèi)者cj就可以貨架取走產(chǎn)品消就可以貨架取走產(chǎn)品消費(fèi)，每次取走一個(gè)。費(fèi)，每次取走一個(gè)。所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費(fèi)者的產(chǎn)品消費(fèi)都可所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費(fèi)者的產(chǎn)品消費(fèi)都可以按自己的意愿進(jìn)行，即相互之間是獨(dú)立的。以按自己的意愿進(jìn)行，即相互之間是獨(dú)立的。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4.1 生產(chǎn)者生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題約束條件約束條件不允許消費(fèi)者從空貨架取產(chǎn)品，現(xiàn)

23、實(shí)中也是取不不允許消費(fèi)者從空貨架取產(chǎn)品，現(xiàn)實(shí)中也是取不到的。到的。不允許生產(chǎn)者向一個(gè)已裝滿產(chǎn)品的貨架中再放入不允許生產(chǎn)者向一個(gè)已裝滿產(chǎn)品的貨架中再放入產(chǎn)品。產(chǎn)品。應(yīng)用背景應(yīng)用背景是對(duì)操作系統(tǒng)中并發(fā)進(jìn)程同步的一種抽象描述，是對(duì)操作系統(tǒng)中并發(fā)進(jìn)程同步的一種抽象描述，多個(gè)進(jìn)程雖然看起來(lái)是按異步方式執(zhí)行的，但相多個(gè)進(jìn)程雖然看起來(lái)是按異步方式執(zhí)行的，但相互有關(guān)的進(jìn)程應(yīng)有一種協(xié)調(diào)機(jī)制?；ビ嘘P(guān)的進(jìn)程應(yīng)有一種協(xié)調(diào)機(jī)制。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題問題描述問題描述哲學(xué)家的生活除了吃面條就是思考問題。哲學(xué)家的生活除了吃面條就是思考問題。吃面條的時(shí)候需要左、右手各拿起一

24、支筷子。吃面條的時(shí)候需要左、右手各拿起一支筷子。吃完后將筷子放回原處，繼續(xù)思考問題。吃完后將筷子放回原處，繼續(xù)思考問題。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題一個(gè)哲學(xué)家的活動(dòng)進(jìn)程表示一個(gè)哲學(xué)家的活動(dòng)進(jìn)程表示思考問題。思考問題。餓了停止思考，左手拿一支筷子（拿不到就等）。餓了停止思考，左手拿一支筷子（拿不到就等）。右手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等） 。進(jìn)餐。進(jìn)餐。放右手筷子。放右手筷子。放左手筷子。放左手筷子。重新回到思考問題狀態(tài)。重新回到思考問題狀態(tài)。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論(2009)8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題可能出現(xiàn)的問題可能出現(xiàn)的問題當(dāng)所有的哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有的哲學(xué)當(dāng)所有的哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無(wú)法進(jìn)餐，最終餓死。家都將無(wú)法進(jìn)餐，最終餓死。將哲學(xué)家的活動(dòng)進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿不將哲學(xué)家的活動(dòng)進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時(shí)，就放下左手的筷子。