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

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

2、一個人怎樣不重復(fù)地走完七座橋，最后還能回到原出發(fā)地點？發(fā)地點？ 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.1.1 8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題歐拉研究了歐拉研究了哥尼斯堡哥尼斯堡七橋問題七橋問題1736年，年，歐拉論證了該問題無解歐拉論證了該問題無解。從一點出發(fā)不重復(fù)地走遍從一點出發(fā)不重復(fù)地走遍7座橋，最后又回到原來出發(fā)點座橋，最后又回到原來出發(fā)點是不可能的。是不可能的。歐拉對問題進行了抽象歐拉對問題進行了抽象 描述：用描述：用4個字母個字母A、B、 C、D代表代表4個城區(qū)，并用個城區(qū)，并用 7條邊表示條邊表示7座橋。座橋。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)歐

3、拉的歐拉的3 3條判定規(guī)則條判定規(guī)則如果如果通奇數(shù)座橋的地方不止兩個通奇數(shù)座橋的地方不止兩個，滿足要求的路徑是找，滿足要求的路徑是找不到的。不到的。如果如果只有兩個地方通奇數(shù)座橋只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一，可以從這兩個地方之一出發(fā)，找到所要求的路徑。出發(fā)，找到所要求的路徑。如果如果沒有一個地方是通奇數(shù)座橋的沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，則無論從哪里出發(fā)，所要求的路徑都能實現(xiàn)。所要求的路徑都能實現(xiàn)。8.1.1 8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)歐拉圖歐拉圖經(jīng)過圖中每條邊一次且僅一次的路徑稱為經(jīng)過圖中每條邊一

4、次且僅一次的路徑稱為歐拉路徑歐拉路徑。如果歐拉路徑的起點和終點為圖中的同一個頂點，這時如果歐拉路徑的起點和終點為圖中的同一個頂點，這時的歐拉路徑稱為的歐拉路徑稱為歐拉回路歐拉回路。包含有歐拉回路的圖稱為包含有歐拉回路的圖稱為歐拉圖歐拉圖。8.1.1 8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)歐拉的研究工作奠定了圖論的基礎(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)域計算機網(wǎng)絡(luò)性能分析計算機網(wǎng)絡(luò)性能分析交通運輸網(wǎng)絡(luò)調(diào)度交通運輸網(wǎng)絡(luò)調(diào)度地下管網(wǎng)配置地下管網(wǎng)配置社會網(wǎng)絡(luò)分析社會網(wǎng)絡(luò)分析8.

5、1.1 8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題航空網(wǎng)絡(luò) 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.1.2 8.1.2 哈密頓回路問題哈密頓回路問題問題描述（周游世界游戲）問題描述（周游世界游戲）找一條從某個城市出發(fā)，找一條從某個城市出發(fā)，經(jīng)過每個城市恰好一次經(jīng)過每個城市恰好一次，最后回到出發(fā)地的路徑。最后回到出發(fā)地的路徑。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)哈密頓回路與歐拉回路的區(qū)別哈密頓回路與歐拉回路的區(qū)別哈密頓回路哈密頓回路是訪問圖的每個頂點一次，而是訪問圖的每個頂點一次，而歐拉回路歐拉回路是訪問圖的每條邊一次。是訪問圖的每條邊一次。對于一個圖是否存在對于一個圖是否存

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

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

8、部移到第三根柱子上。到第三根柱子上。64個盤子63個盤子 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.2.1 8.2.1 漢諾塔問題漢諾塔問題移動規(guī)則移動規(guī)則每次只能移動一個盤子。每次只能移動一個盤子。盤子只能在三根柱子上移動，不能放在他處。盤子只能在三根柱子上移動，不能放在他處。在移動過程中，三根柱子上的盤子必須始終保持在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。大盤在下，小盤在上。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)遞歸思想遞歸思想將一個較大的問題的求解將一個較大的問題的求解歸約為一個或多個子問題歸約為一個或多個子問題的求解的求解。而這些子問題比原問題簡單，

9、且在結(jié)構(gòu)上。而這些子問題比原問題簡單，且在結(jié)構(gòu)上與原問題相同。與原問題相同。從前有座山 從前有座山 從前有座山8.2.1 8.2.1 漢諾塔問題漢諾塔問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.2.18.2.1 漢諾塔問題漢諾塔問題用遞歸方法求解用遞歸方法求解移動移動n個盤子的漢諾塔問題需要移動的盤子數(shù)是個盤子的漢諾塔問題需要移動的盤子數(shù)是n-1個盤個盤子的漢諾塔問題需要移動的盤子數(shù)的子的漢諾塔問題需要移動的盤子數(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+

10、22+2+1 =2n-1+22+2+1 =2 2n n-1-1 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.2.1 8.2.1 漢諾塔問題漢諾塔問題用遞歸方法求解用遞歸方法求解每次只能移動一個盤子，要完成漢諾塔的搬遷，每次只能移動一個盤子，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為：需要移動盤子的次數(shù)為： 264-1=18 446 744 073 709 551 615每秒移動一次，需要大約每秒移動一次，需要大約58495849億年億年的時間。的時間。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.2.28.2.2 旅行商問題旅行商問題問題描述問題描述一旅行商從某城市出發(fā)，必須經(jīng)過每個城市

11、且只能經(jīng)過一次，最后回一旅行商從某城市出發(fā)，必須經(jīng)過每個城市且只能經(jīng)過一次，最后回到原出發(fā)城市。到原出發(fā)城市。要求找到一條距離最短的路徑要求找到一條距離最短的路徑（或費用最少的路徑）。（或費用最少的路徑）。原始的解決辦法原始的解決辦法列出每條可能的路徑列出每條可能的路徑從中選擇距離最短的路徑從中選擇距離最短的路徑 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.2.2 8.2.2 旅行商問題旅行商問題遇到的困難遇到的困難城市個數(shù)較多時難以實現(xiàn)城市個數(shù)較多時難以實現(xiàn)組合爆炸問題組合爆炸問題可行的解決辦法可行的解決辦法啟發(fā)式算法啟發(fā)式算法近似算法近似算法 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014

12、)8.2.3 8.2.3 NPNP完全問題完全問題P P類問題類問題將所有可以在多項式時間內(nèi)求解的問題稱為將所有可以在多項式時間內(nèi)求解的問題稱為P P類問題類問題。 NPNP類問題類問題將所有在多項式時間內(nèi)可以驗證的問題稱為將所有在多項式時間內(nèi)可以驗證的問題稱為NPNP類問題類問題。 NPNP完全問題完全問題在在NP類問題中，某些問題的復(fù)雜性與整個類的復(fù)雜性有類問題中，某些問題的復(fù)雜性與整個類的復(fù)雜性有關(guān)，如果這些問題中的任意一個能在多項式的時間內(nèi)求關(guān)，如果這些問題中的任意一個能在多項式的時間內(nèi)求解，則所有解，則所有NP類問題都能在多項式時間內(nèi)求解，這些類問題都能在多項式時間內(nèi)求解，這些NP類

13、問題稱為類問題稱為NPNP完全問題完全問題。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3 8.3 計算機智能問題計算機智能問題 圖靈測試圖靈測試西爾勒中文小屋西爾勒中文小屋博弈問題博弈問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.1 8.3.1 圖靈測試圖靈測試機器能思維嗎機器能思維嗎 ？ 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.1 8.3.1 圖靈測試圖靈測試圖靈測試游戲圖靈測試游戲游戲的參與者游戲的參與者一個男人、一個女人和一個不限性別的提問者。一個男人、一個女人和一個不限性別的提問者。游戲目標(biāo)游戲目標(biāo)提問者通過對其他兩人的提問，來鑒別其中的男女。提問者通過

14、對其他兩人的提問，來鑒別其中的男女。游戲要求游戲要求提問者呆在與其他兩個游戲者相隔離的房間里。提問者呆在與其他兩個游戲者相隔離的房間里。提問者和兩游戲者之間通過電傳打字機進行溝通。提問者和兩游戲者之間通過電傳打字機進行溝通。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.1 8.3.1 圖靈測試圖靈測試圖靈測試游戲圖靈測試游戲把游戲中的男人換成機器。把游戲中的男人換成機器。若提問者在與機器、女人的游戲中作出的錯誤判斷若提問者在與機器、女人的游戲中作出的錯誤判斷與在男人、女人之間的游戲中作出的錯誤判斷，其與在男人、女人之間的游戲中作出的錯誤判斷，其次數(shù)相同或更多，則判定這部機器能夠思維。次

15、數(shù)相同或更多，則判定這部機器能夠思維。根據(jù)圖靈當(dāng)時的預(yù)測，到根據(jù)圖靈當(dāng)時的預(yù)測，到2000年能有機器通過這樣年能有機器通過這樣的測試。有人認(rèn)為，在的測試。有人認(rèn)為，在1997年戰(zhàn)勝國際象棋大師卡年戰(zhàn)勝國際象棋大師卡斯帕羅夫的斯帕羅夫的深藍計算機深藍計算機可以看作通過了圖靈測試。可以看作通過了圖靈測試。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋問題描述問題描述西爾勒被關(guān)在一個小屋中，屋子里有序地堆放著足西爾勒被關(guān)在一個小屋中，屋子里有序地堆放著足夠的中文字符，而他對中文一竅不通。夠的中文字符，而他對中文一竅不通。屋外的人遞進一串中文字符，同

16、時還附有一本用英屋外的人遞進一串中文字符，同時還附有一本用英文編寫的文編寫的處理中文字符的規(guī)則處理中文字符的規(guī)則，這些規(guī)則將遞進來，這些規(guī)則將遞進來的字符和小屋中的字符之間的轉(zhuǎn)換作了的字符和小屋中的字符之間的轉(zhuǎn)換作了形式化形式化的規(guī)的規(guī)定。定。西爾勒按照規(guī)則對這些字符進行處理后，將一串新西爾勒按照規(guī)則對這些字符進行處理后，將一串新的中文字符送出屋外。的中文字符送出屋外。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋問題描述問題描述實際上，送進來的字符串就是屋外人提出的實際上，送進來的字符串就是屋外人提出的問題問題，送出去的字符串就是所提出問題

17、的送出去的字符串就是所提出問題的答案答案。但。但西爾勒西爾勒并不清楚自己在做什么？并不清楚自己在做什么？ 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋西爾勒的觀點西爾勒的觀點形式化的計算機僅有語法，沒有語義，只是按規(guī)形式化的計算機僅有語法，沒有語義，只是按規(guī)則辦事，并不理解規(guī)則的含義及自己在做什么？則辦事，并不理解規(guī)則的含義及自己在做什么？機器永遠也不可能代替人腦機器永遠也不可能代替人腦。圖靈的觀點圖靈的觀點不要求機器與人腦在內(nèi)部構(gòu)造上一樣，只要與人不要求機器與人腦在內(nèi)部構(gòu)造上一樣，只要與人腦有相同的功能就認(rèn)為腦有相同的功能就認(rèn)為機器有思維機

18、器有思維。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)人工智能的含義人工智能的含義研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能研究的目標(biāo)人工智能研究的目標(biāo)使機器能夠勝任一些通常需要使機器能夠勝任一些通常需要人類智能人類智能才能完成的復(fù)雜才能完成的復(fù)雜工作。工作。 8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)人工智能的不同觀點人工智能的不同觀點符號主義符號主義：人的認(rèn)知基元是符號，人是一個物理符號系人的認(rèn)知

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

20、人工智能的展望人工智能的展望目前人們對心理學(xué)和生物學(xué)的認(rèn)識還很不成熟，對人目前人們對心理學(xué)和生物學(xué)的認(rèn)識還很不成熟，對人腦的結(jié)構(gòu)還沒有真正了解，無法建立起腦的結(jié)構(gòu)還沒有真正了解，無法建立起人腦思維完整人腦思維完整的數(shù)學(xué)模型的數(shù)學(xué)模型。讓計算機具有和人腦完全一樣的智能，不是短期內(nèi)能讓計算機具有和人腦完全一樣的智能，不是短期內(nèi)能夠?qū)崿F(xiàn)的。夠?qū)崿F(xiàn)的。在相當(dāng)長的時間內(nèi)，只能從不同的側(cè)面、以不同的方在相當(dāng)長的時間內(nèi)，只能從不同的側(cè)面、以不同的方式讓計算機具有某些類似人的智能。式讓計算機具有某些類似人的智能。8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)

21、8.3.3 8.3.3 博弈問題博弈問題博弈的含義博弈的含義狹義上講，博弈是指下棋、玩撲克牌、擲骰子等狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲。具有輸贏性質(zhì)的游戲。廣義上講，博弈就是廣義上講，博弈就是對策或斗智對策或斗智。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.3.3 8.3.3 博弈問題博弈問題雙人完備博弈雙人完備博弈兩位選手對壘，輪流走步，其中一方完全知道另兩位選手對壘，輪流走步，其中一方完全知道另一方已經(jīng)走過的棋步以及未來可能的棋步。一方已經(jīng)走過的棋步以及未來可能的棋步。對弈的結(jié)果要么是一方贏（另一方輸），要么是對弈的結(jié)果要么是一方贏（另一方輸），要么是和局

22、。和局。對于任何一種雙人完備博弈，都可以用一個對于任何一種雙人完備博弈，都可以用一個博弈博弈樹樹來描述，并通過博弈樹搜索策略尋找最佳解。來描述，并通過博弈樹搜索策略尋找最佳解。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)博弈樹博弈樹博弈樹類似于狀態(tài)圖和問題求解搜索中使用的搜索博弈樹類似于狀態(tài)圖和問題求解搜索中使用的搜索樹。樹。搜索樹上的一個結(jié)點對應(yīng)一個棋局，樹的分支表示搜索樹上的一個結(jié)點對應(yīng)一個棋局，樹的分支表示棋的走步，根結(jié)點表示棋局的開始，葉結(jié)點表示棋棋的走步，根結(jié)點表示棋局的開始，葉結(jié)點表示棋局的結(jié)束。局的結(jié)束。博弈樹是非常大的博弈樹是非常大的，國際象棋有，國際象棋有10120個結(jié)點，

23、中國個結(jié)點，中國象棋來有象棋來有10160個結(jié)點，個結(jié)點，快速搜索非常重要快速搜索非常重要。8.3.3 8.3.3 博弈問題博弈問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)中國象棋博弈樹中國象棋博弈樹8.3.3 8.3.3 博弈問題博弈問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4 8.4 并發(fā)控制問題并發(fā)控制問題 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題哲學(xué)家共餐問題哲學(xué)家共餐問題 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4.1 8.4.1 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題問題描述問題描述有有n個生產(chǎn)者和個生產(chǎn)者和m個消費者，在生產(chǎn)者和消費者之間個消費者，在生產(chǎn)者

24、和消費者之間設(shè)置了一個能存放設(shè)置了一個能存放k個產(chǎn)品的貨架。個產(chǎn)品的貨架。只要貨架未滿，生產(chǎn)者只要貨架未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)品就可以放入貨架，生產(chǎn)的產(chǎn)品就可以放入貨架，每次放入一個產(chǎn)品；每次放入一個產(chǎn)品；只要貨架非空，消費者只要貨架非空，消費者cj就可以貨架取走產(chǎn)品消費，就可以貨架取走產(chǎn)品消費，每次取走一個。每次取走一個。所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費者的產(chǎn)品消費都可以所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費者的產(chǎn)品消費都可以按自己的意愿進行，即相互之間是獨立的。按自己的意愿進行，即相互之間是獨立的。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4.1 8.4.1 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題約

25、束條件約束條件不允許消費者從空貨架取產(chǎn)品，現(xiàn)實中也是取不到的。不允許消費者從空貨架取產(chǎn)品，現(xiàn)實中也是取不到的。不允許生產(chǎn)者向一個已裝滿產(chǎn)品的貨架中再放入產(chǎn)品。不允許生產(chǎn)者向一個已裝滿產(chǎn)品的貨架中再放入產(chǎn)品。應(yīng)用背景應(yīng)用背景是對操作系統(tǒng)中是對操作系統(tǒng)中并發(fā)進程同步并發(fā)進程同步的一種抽象描述，多個的一種抽象描述，多個進程雖然看起來是按異步方式執(zhí)行的，但相互有關(guān)的進程雖然看起來是按異步方式執(zhí)行的，但相互有關(guān)的進程應(yīng)有一種協(xié)調(diào)機制。進程應(yīng)有一種協(xié)調(diào)機制。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4.2 8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題問題描述問題描述哲學(xué)家的生活除了吃面條就是思考問題。

26、哲學(xué)家的生活除了吃面條就是思考問題。吃面條的時候需要左、右手各拿起一支筷子。吃面條的時候需要左、右手各拿起一支筷子。吃完后將筷子放回原處，繼續(xù)思考問題。吃完后將筷子放回原處，繼續(xù)思考問題。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4.2 8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題一個哲學(xué)家的活動進程表示一個哲學(xué)家的活動進程表示思考問題。思考問題。餓了停止思考，左手拿一支筷子（拿不到就等）。餓了停止思考，左手拿一支筷子（拿不到就等）。右手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等） 。進餐。進餐。放右手筷子。放右手筷子。放左手筷子。放左手筷子。重新回到思考問題狀態(tài)。重新回到思考問題狀態(tài)。 計算機導(dǎo)論計算機導(dǎo)論(2014)(2014)8.4.2 8.4.2 哲學(xué)家共餐問題哲學(xué)家共餐問題可能出現(xiàn)的問題可能出現(xiàn)的問題當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進餐，稱為家都將無法進餐，稱為死鎖狀態(tài)死鎖狀態(tài)。將哲學(xué)家的活動進程修改一下，