計(jì)算機(jī)科學(xué)典型問題示例課件

1、計(jì)算機(jī)科學(xué)典型問題示例計(jì)算機(jī)科學(xué)典型問題示例 哥尼斯堡七橋問題 尋找走遍這7座橋且只許走過每座橋一次，最后又回到原出發(fā)點(diǎn)的路徑 計(jì)算機(jī)科學(xué)典型問題示例 哥尼斯堡七橋問題 兩岸的陸地與河中的小島，都是橋梁的連接點(diǎn)，它們的大小、形狀均與問題本身無關(guān)。因此，把它們看作是4個(gè)點(diǎn)；7座橋是7條必須經(jīng)過的路線，它們的長(zhǎng)短、曲直，也與問題本身無關(guān)。因此，任意畫7條線來表示它們。 歐拉將七橋問題抽象成了一個(gè)“一筆畫”問題。怎樣不重復(fù)地通過7座橋，變成了怎樣不重復(fù)地畫出一個(gè)幾何圖形的問題。原先，人們是要求找出一條不重復(fù)的路線，歐拉接下來著手判斷：這種不重復(fù)的路線究竟存在不存在？由于這么改變了一下提問的角度，歐拉

2、抓住了問題的實(shí)質(zhì)。歐拉發(fā)現(xiàn)，凡是能用一筆畫成的圖形，都有這樣一個(gè)特點(diǎn)：每當(dāng)你用筆畫一條線進(jìn)入中間的一個(gè)點(diǎn)時(shí)，你還必須畫一條線離開這個(gè)點(diǎn)。否則，整個(gè)圖形就不可能用一筆畫出。也就是說，單獨(dú)考察圖中的任何一個(gè)點(diǎn)（除起點(diǎn)和終點(diǎn)外），它都應(yīng)該與偶數(shù)條線相連；如果起點(diǎn)與終點(diǎn)重合，那么，連這個(gè)點(diǎn)也應(yīng)該與偶數(shù)條線相連。 計(jì)算機(jī)科學(xué)典型問題示例 哥尼斯堡七橋問題 計(jì)算機(jī)科學(xué)典型問題示例 哥尼斯堡七橋問題 結(jié)論（1）如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路線是找不到的；（2）如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路線；（3）如果沒有一個(gè)地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路

3、線都能實(shí)現(xiàn)。漢諾塔問題1）每次只能移動(dòng)一個(gè)盤子；2）盤子只能在三根柱子上來回移動(dòng)不能放在他處 ；3）在移動(dòng)過程中三根柱子上的盤子必須始終保持大盤在下小盤在上 天神說，當(dāng)這64個(gè)盤子全部移到第三根柱子上后，世界末日就要到了。 用計(jì)算機(jī)求解一個(gè)實(shí)際問題，首先要從這個(gè)實(shí)際問題中抽象出一個(gè)數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后根據(jù)算法編寫程序，經(jīng)過調(diào)試和運(yùn)行，從而完成該問題的求解。從實(shí)際問題抽象出一個(gè)數(shù)學(xué)模型的實(shí)質(zhì)，其實(shí)就是要用數(shù)學(xué)的方法抽取問題主要的、本質(zhì)的內(nèi)容，最終實(shí)現(xiàn)對(duì)該問題的正確認(rèn)識(shí)。根據(jù)遞歸方法，我們可以將64個(gè)盤子的漢諾塔問題轉(zhuǎn)化為求解63個(gè)盤子的漢諾塔問題，如果63個(gè)盤子的漢諾塔

4、問題能夠解決，則可以將63個(gè)盤子先移動(dòng)到第二個(gè)柱子上，再將最后一個(gè)盤子直接移動(dòng)到第三個(gè)柱子上，最后又一次將63個(gè)盤子從第二個(gè)柱子移動(dòng)到第三個(gè)柱子上。漢諾塔問題示意圖63個(gè)盤子的漢諾塔求解問題可以轉(zhuǎn)化為62個(gè)盤子的漢諾塔求解問題，62個(gè)盤子的漢諾塔求解問題又可以轉(zhuǎn)化為61個(gè)盤子的漢諾塔求解問題，直到1個(gè)盤子的漢諾塔求解問題。再由1個(gè)盤子的漢諾塔的解求出2個(gè)盤子的漢諾塔，直到解出64個(gè)盤子的漢諾塔問題。 因此，要完成漢諾塔的搬遷，需要移動(dòng)盤子的次數(shù)為： 264-1=18446744073709551615 如果每秒移動(dòng)一次，一年有31536000秒，則僧侶們一刻不停地來回搬動(dòng)，也需要花費(fèi)大約584

5、9億年的時(shí)間。假定計(jì)算機(jī)以每秒1000萬個(gè)盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時(shí)間。證比求易算法問題 算法分析是計(jì)算機(jī)科學(xué)的一項(xiàng)主要工作。為了進(jìn)行算法比較，我們必須給出算法效率的某種衡量標(biāo)準(zhǔn)。艾述國(guó)王十分精于計(jì)算，他一秒鐘就算完一個(gè)數(shù)?？墒牵麖脑绲酵?，共算了三萬多個(gè)數(shù)，最終還是沒有結(jié)果。國(guó)王向公主求情，公主將答案相告：223 092 827是它的一個(gè)真因子。國(guó)王很快就驗(yàn)證了這個(gè)數(shù)確能除盡48 770 428 433 377 171。公主說：“我再給你一次機(jī)會(huì)，如果還求不出，將來你只好做我的證婚人了”。國(guó)王立即回國(guó)，召見宰相孔喚石，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位，如果這個(gè)

6、數(shù)可以分成兩個(gè)真因子的乘積，則最小的一個(gè)真因子不會(huì)超過9位。于是他給國(guó)王出了一個(gè)主意：按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)號(hào)發(fā)下去，等公主給出數(shù)目后，立即將它們通報(bào)全國(guó)，讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù)，除盡了立即上報(bào)，賞黃金萬兩。于是，國(guó)王發(fā)動(dòng)全國(guó)上下的民眾，再度求婚，終于取得成功。 在“證比求易算法”的故事中，國(guó)王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時(shí)間方面，后來由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們認(rèn)為順序算法解決不了的問題完全可以用并行算法來解決，甚至?xí)?，并行?jì)算機(jī)系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實(shí)這是一

7、種誤解。國(guó)王有眾多百姓的幫助，求親成功是自然的事。但是，如果換成是一個(gè)貧民百姓的小伙子去求婚，那就困難了。不過，小伙子可以從國(guó)王求親取得成功所采用的并行算法中得到一個(gè)啟發(fā)，那就是：他可以隨便猜一個(gè)數(shù)，然后驗(yàn)證這個(gè)數(shù)。當(dāng)然，這樣做成功的可能性很小，不過，萬一小伙子運(yùn)氣好猜著了呢？由于一個(gè)數(shù)和它的因子之間存在一些有規(guī)律的聯(lián)系，因此，數(shù)論知識(shí)水平較高的人猜中的可能性就大。在算法計(jì)算復(fù)雜性的研究中，將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P類問題，而將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題稱為NP類問題，由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，確定性算法是非確定性算法的一個(gè)特例，因此P

8、NP。對(duì)于大多數(shù)實(shí)際問題來說，找到一個(gè)解可能很難，檢驗(yàn)一個(gè)解常常比較容易，所以都屬于NP類問題?，F(xiàn)在計(jì)算機(jī)科學(xué)研究中一個(gè)懸而未決的重要問題是P=?NP。到目前為止，已經(jīng)發(fā)現(xiàn)了一批可計(jì)算但有相當(dāng)難度的問題是屬于NP類問題，并且常通過證明一個(gè)問題與已知屬于NP類中的某個(gè)問題等價(jià)，將其歸入NP類問題。 哲學(xué)家的生活進(jìn)程思考問題餓了停止思考，左手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）進(jìn)餐放右手筷子放左手筷子重新回到思考問題的狀態(tài)1哲學(xué)家的生活進(jìn)程的極端情況：當(dāng)所有哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有哲學(xué)家都拿不到右手的筷子，并處于等待狀態(tài)，則哲學(xué)家將都無法進(jìn)餐，最終餓死；改變進(jìn)程，如拿不到

9、右手筷子則放下左手筷子。在某一瞬可能所有的哲學(xué)家都拿起左手的筷子，因拿不到右手的筷子又都同時(shí)放下左手的筷子，如此下去，所有的哲學(xué)家同樣無法進(jìn)餐。哲學(xué)家進(jìn)餐問題在計(jì)算機(jī)科學(xué)中所反映的問題：程序并發(fā)執(zhí)行時(shí)進(jìn)程同步的問題：死鎖（Deadlock）和饑餓（Starvation）為了提高系統(tǒng)的處理能力和機(jī)器的利用率，并法程序被廣泛地使用，因此必須徹底解決并發(fā)進(jìn)程中的死鎖和饑餓問題StarvationStarvationStarvation旅行商問題旅行商問題（Traveling Salesman Problem，簡(jiǎn)稱TSP）是威廉哈密爾頓（W.R.Hamilton）爵士和英國(guó)數(shù)學(xué)家克克曼（T.P.Kir

10、kman）于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問題。這是一個(gè)典型的NP完全性問題。其大意是：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線，使其旅行的費(fèi)用最少。人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原始的一種方法是：列出每一條可供選擇的路線（即對(duì)給定的城市進(jìn)行排列組合），計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個(gè)城市分別為A、B、C和D，各城市之間的距離為已知數(shù)，如圖a、圖b所示。從圖中可以看到，可供選擇的路線共有6條，從中很快可以選出一條總距離最短

11、的路線。ABCD256424圖a 城市交通圖A265BCD244442BDCCBD224444ACCBDBD522665圖b 組合路徑圖設(shè)城市數(shù)目為n時(shí)，那么組合路徑數(shù)則為（n-1）！。很顯然，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)急劇增長(zhǎng)，以至達(dá)到無法計(jì)算的地步，這就是所謂的“組合爆炸問題”。假設(shè)現(xiàn)在城市的數(shù)目增為20個(gè)，組合路徑數(shù)則為（20-1）！1.2161017，如此龐大的組合數(shù)目，若計(jì)算機(jī)以每秒檢索1000萬條路線的速度計(jì)算，也需要花上386年的時(shí)間。 圖靈測(cè)試問題 在計(jì)算機(jī)學(xué)科誕生后，為解決人工智能中一些激烈爭(zhēng)論的問題，圖靈和西爾

12、勒又分別提出了能反映人工智能本質(zhì)特征的兩個(gè)著名的哲學(xué)問題，即“圖靈測(cè)試”和西爾勒的“中文屋子”，沿著圖靈等人對(duì)“智能”的理解，人們?cè)谌斯ぶ悄茴I(lǐng)域取得了長(zhǎng)足的進(jìn)展，其中“深藍(lán)（Deep Blue）”戰(zhàn)勝國(guó)際象棋大師卡斯帕羅夫（G.Kasparov）就是一個(gè)很好的例證。 圖靈于1950年在英國(guó) Mind雜志上發(fā)表了Computing Machinery and Intelligence一文，文中提出了“機(jī)器能思維嗎？”這樣一個(gè)問題，并給出了一個(gè)被后人稱之為“圖靈測(cè)試（Turing Test）”的模仿游戲。 這個(gè)游戲由3個(gè)人來完成：一個(gè)男人（A），一個(gè)女人（B），一個(gè)性別不限的提問者（C）。提問者（

13、C）呆在與其他兩個(gè)游戲者相隔離的房間里。游戲的目標(biāo)是讓提問者通過對(duì)其他兩人的提問來鑒別其中哪個(gè)是男人，哪個(gè)是女人。為了避免提問者通過他們的聲音、語調(diào)輕易地作出判斷，最好是在提問者和兩游戲者之間通過一臺(tái)電傳打字機(jī)來進(jìn)行溝通。提問者只被告知兩個(gè)人的代號(hào)為X和Y，游戲的最后他要作出“X是A，Y是B”或“X是B，Y是A”的判斷。 現(xiàn)在，把上面這個(gè)游戲中的男人（A）換成一部機(jī)器來扮演，如果提問者在與機(jī)器、女人的游戲中作出的錯(cuò)誤判斷與在男人、女人之間的游戲中作出錯(cuò)誤判斷的次數(shù)是相同的，那么，就可以判定這部機(jī)器是能夠思維的。 圖靈關(guān)于“圖靈測(cè)試”的論文發(fā)表后引發(fā)了很多的爭(zhēng)論，以后的學(xué)者在討論機(jī)器思維時(shí)大多都

14、要談到這個(gè)游戲。 “圖靈測(cè)試”只是從功能的角度來判定機(jī)器是否能思維，也就是從行為主義角度來對(duì)“機(jī)器思維”進(jìn)行定義。盡管圖靈對(duì)“機(jī)器思維”的定義是不夠嚴(yán)謹(jǐn)?shù)?，但他關(guān)于“機(jī)器思維”定義的開創(chuàng)性工作對(duì)后人的研究具有重要意義，因此，一些學(xué)者認(rèn)為，圖靈發(fā)表的關(guān)于“圖靈測(cè)試”的論文標(biāo)志著現(xiàn)代機(jī)器思維問題討論的開始。 根據(jù)圖靈的預(yù)測(cè)，到2000年，此類機(jī)器能通過測(cè)試?，F(xiàn)在，在某些特定的領(lǐng)域，如博弈領(lǐng)域，“圖靈測(cè)試”已取得了成功，1997年，IBM公司研制的計(jì)算機(jī)“深藍(lán)”就戰(zhàn)勝了國(guó)際象棋冠軍卡斯帕羅夫。 在未來，如果我們能像圖靈揭示計(jì)算本質(zhì)那樣揭示人類思維的本質(zhì)，即“能行”思維，那么制造真正思維機(jī)器的日子也就

15、不長(zhǎng)了?？上б獙?duì)人類思維的本質(zhì)進(jìn)行描述，還是相當(dāng)遙遠(yuǎn)的事情。 搏弈問題 博弈問題屬于人工智能中一個(gè)重要的研究領(lǐng)域。從狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲；從廣義上講，博弈就是對(duì)策或斗智。計(jì)算機(jī)中的博弈問題，一直是人工智能領(lǐng)域研究的重點(diǎn)內(nèi)容之一。 1913年，數(shù)學(xué)家策墨洛（E.Zermelo）在第五屆國(guó)際數(shù)學(xué)會(huì)議上發(fā)表了關(guān)于集合論在象棋博弈理論中的應(yīng)用（On an Application of Set Theory to Game of Chess）的著名論文，第一次把數(shù)學(xué)和象棋聯(lián)系起來，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個(gè)新的理論，即博弈論。 1950年，“信息論”創(chuàng)始人香農(nóng)（A.

16、Shannon）發(fā)表了國(guó)際象棋與機(jī)器（A ChessPlaying Machine）一文，并闡述了用計(jì)算機(jī)編制下棋程序的可能性。 1956年夏天，由麥卡錫（J.McCarthy）和香農(nóng)等人共同發(fā)起的，在美國(guó)達(dá)特茅斯（Dartmouth）大學(xué)舉行的夏季學(xué)術(shù)討論會(huì)上，第一次正式使用了“人工智能”這一術(shù)語，該次會(huì)議的召開對(duì)人工智能的發(fā)展起到了極大的推動(dòng)作用。 當(dāng)時(shí)，IBM公司的工程師塞繆爾（A. Samuel）也被邀請(qǐng)參加了“達(dá)特茅斯”會(huì)議，塞繆爾的研究專長(zhǎng)正是電腦下棋。早在1952年，塞繆爾就運(yùn)用博弈理論和狀態(tài)空間搜索技術(shù)成功地研制了世界上第一個(gè)跳棋程序。該程序經(jīng)不斷地完善于1959年擊敗了它的設(shè)

17、計(jì)者塞繆爾本人，1962年，它又擊敗了美國(guó)一個(gè)州的冠軍 。 1970年開始，ACM每年舉辦一次計(jì)算機(jī)國(guó)際象棋錦標(biāo)賽直到1994年（1992年中斷過一次），每年產(chǎn)生一個(gè)計(jì)算機(jī)國(guó)際象棋賽冠軍，1991年，冠軍由IBM的“深思（Deep Thought）”獲得。ACM的這些工作極大地推動(dòng)了博弈問題的深入研究，并促進(jìn)了人工智能領(lǐng)域的發(fā)展。北京時(shí)間1997年5月初，在美國(guó)紐約公平大廈，“深藍(lán)”與國(guó)際象棋冠軍卡斯帕羅夫交戰(zhàn)，前者以兩勝一負(fù)三平戰(zhàn)勝后者。 “深藍(lán)”是美國(guó)IBM公司研制的一臺(tái)高性能并行計(jì)算機(jī)，它由256（32 node*8）個(gè)專為國(guó)際象棋比賽設(shè)計(jì)的微處理器組成，據(jù)估計(jì)，該系統(tǒng)每秒可計(jì)算2億步棋?！吧钏{(lán)”的前身是“深思”，始建于1985年。1989年，卡斯帕羅夫首戰(zhàn)“深思”，后者敗北。1996年，在“深思”基礎(chǔ)上研制出的“深藍(lán)”曾再次與卡斯帕羅夫交戰(zhàn)，并以2：4負(fù)于對(duì)手。國(guó)際象棋、西洋跳棋與圍棋、中國(guó)象棋一樣都屬于雙人完備博弈。 所謂雙人完備博弈就是兩位選手對(duì)壘，輪流走步，其中一方完全知道另一方已經(jīng)走過的棋步以及未來可能的走步，對(duì)弈的結(jié)果要么是一方贏（另一方輸），要么是和局。對(duì)于任何一種雙人完備博弈，都可以用一個(gè)博弈樹（與或樹）來