計(jì)算機(jī)導(dǎo)論（第5版） 課件 第11章-計(jì)算機(jī)領(lǐng)域的典型問題

計(jì)算機(jī)導(dǎo)論第11章

計(jì)算機(jī)領(lǐng)域的典型問題目錄CONTENTS03并發(fā)控制問題01圖論問題02算法復(fù)雜性問題圖論問題哥尼斯堡七橋問題；哈密頓回路問題；中國郵路問題/01歌尼斯堡七橋問題問題描述在18世紀(jì)中葉，東普魯士的哥尼斯堡城中有7座橋連接3個(gè)城區(qū)和1個(gè)島區(qū)。城中人們時(shí)常討論的一個(gè)話題：一個(gè)人怎樣不重復(fù)地走完7座橋，最后還能回到原出發(fā)地點(diǎn)？

歌尼斯堡七橋問題歐拉對(duì)哥尼斯堡七橋問題進(jìn)行了研究1736年，歐拉論證了該問題無解。歐拉的結(jié)論：從一點(diǎn)出發(fā)不重復(fù)地走遍7座橋，最后又回到原來出發(fā)點(diǎn)是不可能的。歐拉對(duì)問題進(jìn)行了抽象：用4個(gè)字母A、B、C、D代表4個(gè)城區(qū)，并用7條邊表示7座橋。歌尼斯堡七橋問題歐拉給出了3條判定規(guī)則如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路徑是找不到的。如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到經(jīng)過所有橋一次的路徑。如果沒有一個(gè)地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路徑都能實(shí)現(xiàn)。歌尼斯堡七橋問題歐拉圖經(jīng)過圖中每條邊一次且僅一次的路徑稱為歐拉路徑。如果歐拉路徑的起點(diǎn)和終點(diǎn)為圖中的同一個(gè)頂點(diǎn)，這時(shí)的歐拉路徑稱為歐拉回路。包含有歐拉回路的圖稱為歐拉圖。哈密頓回路問題問題描述（周游世界游戲）找一條從某個(gè)城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后回到出發(fā)地的路徑（哈密頓回路）。哈密頓回路問題哈密頓回路與歐拉回路的區(qū)別哈密頓回路是訪問圖的每個(gè)頂點(diǎn)一次，而歐拉回路是訪問圖的每條邊一次。對(duì)于一個(gè)圖是否存在歐拉回路，已給出充要條件（歐拉的判定規(guī)則）；而對(duì)于一個(gè)圖是否存在哈密頓回路，至今仍未找到充要條件。中國郵路問題問題描述一個(gè)郵遞員應(yīng)如何選擇一條路線，使他能夠從郵局出發(fā)，走遍他負(fù)責(zé)送信的所有街道，最后回到郵局，并且所走的路程最短。歸結(jié)為圖論問題：給定一個(gè)連通無向圖，求該圖的一條經(jīng)過每條邊至少一次的最短回路。對(duì)于歐拉圖，找到一條歐拉回路即可。對(duì)于非歐拉圖，才是中國郵路問題的研究重點(diǎn)。算法復(fù)雜性問題漢諾塔問題；旅行商問題；NP完全問題/02漢諾塔問題問題描述將第一根柱子上的64個(gè)盤子借助第二根柱子全部移到第三根柱子上。漢諾塔問題盤子移動(dòng)規(guī)則每次只能移動(dòng)一個(gè)盤子。盤子只能在三根柱子上移動(dòng)，不能放在他處。在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。漢諾塔問題遞歸思想將一個(gè)較大規(guī)模的問題的求解歸約為一個(gè)或多個(gè)子問題的求解。這些子問題比原問題簡單，且在結(jié)構(gòu)上與原問題相同。漢諾塔問題用遞歸方法求解移動(dòng)n個(gè)盤子的漢諾塔問題，需要移動(dòng)盤子的次數(shù)是n-1個(gè)盤子的漢諾塔問題需要移動(dòng)盤子次數(shù)的2倍加1，即h(n)=2h(n-1)+1。漢諾塔問題用遞歸方法求解（時(shí)間復(fù)雜度為O(2n)）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)一個(gè)盤子，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為：

264-1=18446744073709551615如果每秒移動(dòng)一次，需要大約5849億年的時(shí)間。漢諾塔問題用遞歸方法求解旅行商問題問題描述一旅行商從某城市出發(fā)，必須經(jīng)過每個(gè)城市且只能經(jīng)過一次，最后回到原出發(fā)城市。要求找到一條距離最短的路徑（或費(fèi)用最少的路徑）。簡單問題的解決辦法（4個(gè)城市）列出每條可能的路徑。從中選擇距離最短的路徑。旅行商問題遇到的困難城市個(gè)數(shù)較多時(shí)難以實(shí)現(xiàn)，出現(xiàn)組合爆炸問題。當(dāng)城市個(gè)數(shù)為n時(shí)，組合路徑數(shù)為(n-1)!，算法的復(fù)雜度為O(n!)。如果n=20，則組合路徑數(shù)則為（20-1)！≈1.216×1017。若計(jì)算機(jī)每秒能計(jì)算出1億條路徑的長度，計(jì)算完所有路徑的長度也需要38.6年的時(shí)間?？尚械慕鉀Q辦法最近鄰算法：每次選一個(gè)和所在城市最近的城市。得到的結(jié)果不是最短路徑，是一個(gè)比較短的路徑，但求解問題的復(fù)雜度大大降低。NP完全問題P類問題：將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P類問題。NP類問題：將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題稱為NP類問題。NP完全問題：在NP類問題中，某些問題的復(fù)雜性與整個(gè)類的復(fù)雜性有關(guān)，如果這些問題中的任意一個(gè)能在多項(xiàng)式的時(shí)間內(nèi)求解，則所有NP類問題都能在多項(xiàng)式時(shí)間內(nèi)求解，這些NP類問題稱為NP完全問題。并發(fā)控制問題生產(chǎn)者-消費(fèi)者問題；哲學(xué)家共餐問題/03生產(chǎn)者-消費(fèi)者問題問題描述有n個(gè)生產(chǎn)者和m個(gè)消費(fèi)者，在生產(chǎn)者和消費(fèi)者之間設(shè)置了一個(gè)能存放k個(gè)產(chǎn)品的貨架。只要貨架未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)品就可以放入貨架，每次放入一個(gè)產(chǎn)品；只要貨架非空，消費(fèi)者cj就可以貨架取走產(chǎn)品消費(fèi)，每次取走一個(gè)。所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費(fèi)者的產(chǎn)品消費(fèi)都可以按自己的意愿進(jìn)行，即相互之間是獨(dú)立的。生產(chǎn)者-消費(fèi)者問題約束條件不允許消費(fèi)者從空貨架取產(chǎn)品，現(xiàn)實(shí)中也是取不到的。不允許生產(chǎn)者向一個(gè)已裝滿產(chǎn)品的貨架中再放入產(chǎn)品。應(yīng)用背景是對(duì)操作系統(tǒng)中并發(fā)進(jìn)程同步的一種抽象描述，多個(gè)進(jìn)程雖然看起來是按異步方式執(zhí)行的，但相互有關(guān)的進(jìn)程應(yīng)有一種協(xié)調(diào)機(jī)制。哲學(xué)家共餐問題問題描述圍坐在圓桌旁的5位哲學(xué)家的生活除了用餐（吃面條）就是思考問題。用餐時(shí)需要左、右手各拿起一支筷子。用餐后將筷子放回原處，繼續(xù)思考問題。哲學(xué)家共餐問題一位哲學(xué)家的活動(dòng)進(jìn)程表示思考問題；餓了停止思考，左手拿起一支筷子（拿不到就等)；右手拿起一支筷子（拿不到就等)；進(jìn)餐（用兩支筷子吃面條)；放下右手筷子；放下左手筷子；重新回到思考問題狀態(tài)。哲學(xué)家共餐問題可能出現(xiàn)的問題當(dāng)5位哲學(xué)家都同時(shí)拿起左手邊筷子時(shí)，則5位哲學(xué)家都將拿不到右手邊的筷子，并處于等待狀態(tài)，導(dǎo)致5位哲學(xué)家都將無法進(jìn)餐，此時(shí)稱為死鎖狀態(tài)。將哲學(xué)家的活動(dòng)進(jìn)程修改一下，變?yōu)楫?dāng)右手邊的筷子拿不到時(shí)，就放下左手邊的筷子。可能在一個(gè)瞬間，5位哲學(xué)家都同時(shí)拿起左手邊的筷子，則自然拿不到右手邊的筷子，于是都同時(shí)放下左手的筷子，等一會(huì)，又同時(shí)拿起左手邊的筷子，如此這樣永遠(yuǎn)重復(fù)下去，則所有的哲學(xué)家仍然