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

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

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

4、次且僅一次的路徑稱為歐拉路徑歐拉路徑。如果歐拉路徑的起點和終點為圖中的同一個頂點，這時如果歐拉路徑的起點和終點為圖中的同一個頂點，這時的歐拉路徑稱為的歐拉路徑稱為歐拉回路歐拉回路。包含有歐拉回路的圖稱為包含有歐拉回路的圖稱為歐拉圖歐拉圖。8.1.1 8.1.1 歌尼斯堡七橋問題歌尼斯堡七橋問題 計算機導論計算機導論(2014)(2014)歐拉的研究工作奠定了圖論的基礎歐拉的研究工作奠定了圖論的基礎涉及到的后續課程涉及到的后續課程離散數學離散數學數據結構數據結構應用領域應用領域計算機網絡性能分析計算機網絡性能分析交通運輸網絡調度交通運輸網絡調度地下管網配置地下管網配置社會網絡分析社會網絡分析8.

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

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

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

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

9、且在結構上。而這些子問題比原問題簡單，且在結構上與原問題相同。與原問題相同。從前有座山 從前有座山 從前有座山8.2.1 8.2.1 漢諾塔問題漢諾塔問題 計算機導論計算機導論(2014)(2014)8.2.18.2.1 漢諾塔問題漢諾塔問題用遞歸方法求解用遞歸方法求解移動移動n個盤子的漢諾塔問題需要移動的盤子數是個盤子的漢諾塔問題需要移動的盤子數是n-1個盤個盤子的漢諾塔問題需要移動的盤子數的子的漢諾塔問題需要移動的盤子數的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 計算機導論計算機導論(2014)(2014)8.2.1 8.2.1 漢諾塔問題漢諾塔問題用遞歸方法求解用遞歸方法求解每次只能移動一個盤子，要完成漢諾塔的搬遷，每次只能移動一個盤子，要完成漢諾塔的搬遷，需要移動盤子的次數為：需要移動盤子的次數為： 264-1=18 446 744 073 709 551 615每秒移動一次，需要大約每秒移動一次，需要大約58495849億年億年的時間。的時間。 計算機導論計算機導論(2014)(2014)8.2.28.2.2 旅行商問題旅行商問題問題描述問題描述一旅行商從某城市出發，必須經過每個城市

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

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

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

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

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

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

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

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

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

20、人工智能的展望人工智能的展望目前人們對心理學和生物學的認識還很不成熟，對人目前人們對心理學和生物學的認識還很不成熟，對人腦的結構還沒有真正了解，無法建立起腦的結構還沒有真正了解，無法建立起人腦思維完整人腦思維完整的數學模型的數學模型。讓計算機具有和人腦完全一樣的智能，不是短期內能讓計算機具有和人腦完全一樣的智能，不是短期內能夠實現的。夠實現的。在相當長的時間內，只能從不同的側面、以不同的方在相當長的時間內，只能從不同的側面、以不同的方式讓計算機具有某些類似人的智能。式讓計算機具有某些類似人的智能。8.3.2 8.3.2 西爾勒中文小屋西爾勒中文小屋 計算機導論計算機導論(2014)(2014)

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

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

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

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

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

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