電子教案7-2常見(jiàn)算法

大學(xué)計(jì)算機(jī),第7章：算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),常見(jiàn)算法,7.2,7.2.1窮舉法,窮舉法又稱(chēng)列舉法、枚舉法，是蠻力策略的具體體現(xiàn)，是一種簡(jiǎn)單而直接地解決問(wèn)題的方法。其基本思想是逐一列舉問(wèn)題所涉及的所有情形，并根據(jù)問(wèn)題提出的條件檢驗(yàn)?zāi)男┦菃?wèn)題的解，哪些應(yīng)予排除。窮舉法常用于解決“是否存在”或“有多少種可能”等問(wèn)題。窮舉算法特點(diǎn)是算法簡(jiǎn)單，但運(yùn)行時(shí)所花費(fèi)的時(shí)間量大。例如：有一把鎖和一串鑰匙（共有10把鑰匙），怎樣找出所有開(kāi)這把鎖的鑰匙？在QQ上，OicqPassOver這個(gè)工具窮舉用戶的口令，它根據(jù)機(jī)器性能最高可以每秒測(cè)試20000個(gè)口令，如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯。,7.2.1窮舉法,1、百錢(qián)百雞問(wèn)題中國(guó)古代算書(shū)張丘建的算經(jīng)中有一道著名的百雞問(wèn)題：公雞每只值5文錢(qián)，母雞每只值3文錢(qián)，而3只小雞值1文錢(qián)?，F(xiàn)在用100文錢(qián)買(mǎi)100只雞，問(wèn)：這100只雞中，公雞、母雞和小雞各有多少只？解法如下：設(shè)公雞、母雞、小雞分別為x、y、z只，由題意得：用窮舉法求解，對(duì)每組求得滿足等式方程組的值，從而找到百錢(qián)百雞的解。,7.2.1窮舉法,2、邏輯推斷有四位學(xué)生中的一位做了好事，不留名，表?yè)P(yáng)信來(lái)了之后，校長(zhǎng)問(wèn)這四位是誰(shuí)做的好事。A說(shuō)：不是我。B說(shuō)：是C。C說(shuō)：是D。D說(shuō)：他胡說(shuō)。已知三個(gè)人說(shuō)的是真話，一個(gè)人說(shuō)的是假話?，F(xiàn)在要根據(jù)這些信息，找出做了好事的人?，F(xiàn)在并不知道是誰(shuí)做得好事，但知道做好事的人是A,B,C,D四個(gè)人中的某一個(gè)。因此，可以一個(gè)一個(gè)地試探。這也是通過(guò)窮舉法來(lái)解決問(wèn)題。,7.2.1窮舉法,3、韓信點(diǎn)兵秦朝末年，楚漢相爭(zhēng)。一次，韓信將1500名將士與楚王大將李鋒交戰(zhàn)。他命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。韓信馬上向?qū)⑹總冃?“我軍有1073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人?！睗h軍本來(lái)就信服自己的統(tǒng)帥，這一來(lái)更相信韓信是“神仙下凡”、“神機(jī)妙算”。于是士氣大振。一時(shí)間旌旗搖動(dòng)，鼓聲喧天，漢軍步步進(jìn)逼，楚軍亂作一團(tuán)。交戰(zhàn)不久，楚軍大敗而逃。“韓信點(diǎn)兵”它形成了一類(lèi)問(wèn)題，這個(gè)問(wèn)題計(jì)算機(jī)解決起來(lái)也是用的窮舉法，用從1開(kāi)始逐個(gè)自然數(shù)的試著尋找滿足上述題意要求的值，直到找到這個(gè)數(shù)x為止。,7.2.1窮舉法,用窮舉算法解決問(wèn)題，通常可以從兩個(gè)方面進(jìn)行分析：1、問(wèn)題所涉及的情況：?jiǎn)栴}所涉及的情況有哪些，情況的種數(shù)可不可以確定。把它描述出來(lái)。2、答案需要滿足的條件：分析出來(lái)的這些情況，需要滿足什么條件，才成為問(wèn)題的答案，把這些條件描述出來(lái)。窮舉法窮舉的數(shù)據(jù)量過(guò)大，效率較低，對(duì)于小規(guī)模的問(wèn)題還是適用的但是問(wèn)題規(guī)模一旦擴(kuò)大，窮舉法就沒(méi)有什么可取性了。一般巧妙和高效算法很少來(lái)自窮舉法。,7.2.2回溯法,迷宮游戲,7.2.2回溯法,回溯算法也叫試探法，是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為“回溯點(diǎn)”?；厮莘ǖ闹笇?dǎo)思想：走不通，就掉頭回溯法在搜索過(guò)程中通過(guò)對(duì)約束條件的判定，排除錯(cuò)誤答案，提高了搜索效率。,7.2.2回溯法,1、八皇后問(wèn)題八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。,7.2.2回溯法,回溯法解八皇后問(wèn)題思路：逐行擺放皇后。初始第1行皇后放第1列；擺放第i行皇后時(shí)，從第1列開(kāi)始，逐列判定是否與前i-1行皇后攻擊，直到找到一個(gè)不攻擊的位置，繼續(xù)第i+1行的擺放；若第i行無(wú)擺放位置，則拿掉該行皇后，回溯至第i-1行，第i-1行皇后從當(dāng)前位置的下一列開(kāi)始判定，繼續(xù)搜索。當(dāng)?shù)?行皇后的擺放位置超出棋盤(pán)時(shí)，全部求解過(guò)程結(jié)束，可找到92種擺法。,7.2.2回溯法,網(wǎng)絡(luò)爬蟲(chóng)是一個(gè)功能強(qiáng)大的自動(dòng)提取網(wǎng)頁(yè)的程序，它為搜索引擎從萬(wàn)維網(wǎng)下載網(wǎng)頁(yè)，是搜索引擎的重要組成部分。它可以完全不依賴(lài)用戶干預(yù)實(shí)現(xiàn)網(wǎng)絡(luò)上的自動(dòng)“爬行”和搜索。網(wǎng)絡(luò)爬蟲(chóng)是通過(guò)網(wǎng)頁(yè)的鏈接地址來(lái)尋找網(wǎng)頁(yè)在抓取網(wǎng)頁(yè)的時(shí)候，網(wǎng)絡(luò)爬蟲(chóng)采用了深度優(yōu)先策略。深度優(yōu)先是指網(wǎng)絡(luò)爬蟲(chóng)會(huì)從起始頁(yè)開(kāi)始，一個(gè)鏈接一個(gè)鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個(gè)起始頁(yè)，繼續(xù)跟蹤鏈接。這個(gè)方法有個(gè)優(yōu)點(diǎn)是網(wǎng)絡(luò)爬蟲(chóng)在設(shè)計(jì)的時(shí)候比較容易。這是一種典型的回溯算法。,7.2.2回溯法,回溯法的本質(zhì)也是一種窮舉法，但與窮舉法相比，回溯法的“聰明”之處在于能適時(shí)“回頭”，若再往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無(wú)效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問(wèn)題。,7.2.3遞歸法,人們都熟悉一個(gè)民間故事：從前有一座山，山上有一座廟，廟里有一個(gè)老和尚正在給小和尚講故事，故事里說(shuō)，從前有一座山，山上有一座廟，廟里有一個(gè)老和尚正在給小和尚講故事，故事里說(shuō)。所謂遞歸就是一個(gè)函數(shù)或過(guò)程可以直接或間接地調(diào)用自己。,7.2.3遞歸法,遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱(chēng)為直接遞歸調(diào)用；如果一個(gè)算法A調(diào)用另一個(gè)算法B，而算法B又調(diào)用算法A，則此種遞歸稱(chēng)為間接遞歸調(diào)用。,7.2.3遞歸法,1.n！問(wèn)題階乘可以這樣遞歸地定義成函數(shù)：這樣，所有自然數(shù)的階乘就可以通過(guò)上面的兩句話表示了。2的階乘就是12；3的階乘就是2的階乘乘3，即123不僅如此，人們還可以知道0的階乘是多少，1的階乘應(yīng)該等于0的階乘乘以1，顯然0的階乘必須是1才行。,7.2.3遞歸法,1.n！問(wèn)題每個(gè)遞歸函數(shù)必須至少有一個(gè)基線條件一般情況必須最終能簡(jiǎn)化為基線條件,7.2.3遞歸法,2、漢諾塔（Hanoi）問(wèn)題相傳印度有座大寺廟，它曾被認(rèn)為是宇宙的中心。神廟中放置了一塊上面插有三根長(zhǎng)木釘?shù)哪景澹谄渲械囊桓踞斏?，由上至下放?4片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧侶們將64片金屬片全部移至另一根木釘上。移動(dòng)規(guī)則只有兩個(gè)：（1）在每次的移動(dòng)中，只能移動(dòng)一片金屬片；（2）過(guò)程中任意時(shí)刻必須保證金屬片小的在上，大的在下。,7.2.3遞歸法,使用遞歸時(shí)必須符合以下三個(gè)條件：（1）可將一個(gè)問(wèn)題轉(zhuǎn)化為一個(gè)新的問(wèn)題，而新問(wèn)題的解決方法仍與原問(wèn)題的解法相同，只不過(guò)所處理的對(duì)象有所不同而已，即它們只是有規(guī)律的遞增或遞減。（2）可以通過(guò)轉(zhuǎn)化過(guò)程使問(wèn)題回到對(duì)原問(wèn)題的求解。（3）必須要有一個(gè)明確的結(jié)束遞歸的條件，否則遞歸會(huì)無(wú)止境地進(jìn)行下去。遞歸對(duì)某些問(wèn)題而言存在重復(fù)調(diào)用，導(dǎo)致算法效率不高。,7.2.4分治法,分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。,7.2.4分治法,1、找出偽幣一個(gè)裝有16枚硬幣的袋子，16枚硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這枚偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來(lái)比較兩組硬幣重量的儀器，比如天平。利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。,7.2.4分治法,1、找出偽幣方法1：任意取1枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有15次比較。,7.2.4分治法,1、找出偽幣方法2：將硬幣分為8組，每組2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有8次比較。,7.2.4分治法,1、找出偽幣方法3：,7.2.4分治法,上述三種方法,分別需要比較18次,8次,4次,那么形成比較次數(shù)差異的根據(jù)原因在哪里?方法1:每枚硬幣都至少進(jìn)行了一次比較,而有一枚硬幣進(jìn)行了15次比較方法2:每一枚硬幣只進(jìn)行了一次比較方法3:將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來(lái)的一半,這樣充分地利用了只有1枚偽幣的基本性質(zhì)。,7.2.4分治法,根據(jù)以上比較，第三種方法就是分治法，可以得到以下的采用分治方法的結(jié)論：1、參與比較的硬幣數(shù)量越多，使用該方法來(lái)實(shí)現(xiàn)就越快，而且投機(jī)性大大減少；2、解決方法關(guān)鍵在于能將大問(wèn)題分割成若干小問(wèn)題；3、小問(wèn)題與原有問(wèn)題是完全類(lèi)似的。,7.2.4分治法,2、二分法二分查找又稱(chēng)為折半查找，是一種可在有序順序表上實(shí)現(xiàn)的效率比較高的查找算法。是一個(gè)典型的分治算法。,7.2.4分治法,分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。,7.2.5貪心法,貪心算法（又稱(chēng)貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。只顧眼前利益，每次都選最好的,7.2.5貪心法,1、商場(chǎng)找零假設(shè)只有3種面額的幣值，它們的面值分別為20元、10元、5元、和1元。現(xiàn)要找給某顧客37元，這時(shí)，售貨員幾乎不假思索地拿出1個(gè)20元、1個(gè)l0元、1個(gè)5元和2個(gè)1元的錢(qián)幣交給顧客。人們不僅能很快決定要拿哪些錢(qián)幣，而且與其它找法相比這時(shí)拿出的錢(qián)幣的個(gè)數(shù)肯定是最少的。在這里，收貨員實(shí)際使用了這樣的算法：首先選出一個(gè)面值不超過(guò)37元的最大面額錢(qián)幣（20元），然后從37元中減去20元，剩下17元中再選出一個(gè)不超過(guò)17元的最大面額錢(qián)幣（10元），如此做下去，直到找足37元。這就是所謂的貪心法。,7.2.5貪心法,2、最短路徑頂點(diǎn)為城市，邊上的代價(jià)為兩城市問(wèn)的里程。在圖中找一條經(jīng)過(guò)所有結(jié)點(diǎn)一次的回路，并使里程的總和為最小?？梢园催@樣一個(gè)想法去做：首先在圖中選一條代價(jià)最小的邊。為了選擇下一條邊，先要檢查一下候選邊與已選入的邊之間是否滿足以下兩點(diǎn)：1)不會(huì)有三條邊(候選邊及已入選邊)與同一頂點(diǎn)相關(guān)聯(lián)。2)不會(huì)使入選邊形成回路，除非入選邊的個(gè)數(shù)已等于圖中的頂點(diǎn)總數(shù)。在滿足以上兩點(diǎn)的候選邊中，挑選最短的邊作為入選邊。如此做下去，直到得到一個(gè)經(jīng)過(guò)所有頂點(diǎn)的回路。最后求得的回路是125341，代價(jià)是14。圖中最小代價(jià)的回路是12543一1，代價(jià)是10。這也是典型的貪心策略。,7.2.5貪心法,2、最短路徑可以按這樣一個(gè)想法去做：首先在圖中選一條代價(jià)最小的邊。為了選擇下一條邊，先要檢查一下候選邊與已選入的邊之間是否滿足以下兩點(diǎn)：1)不會(huì)有三條邊(候選邊及已入選邊)與同一頂點(diǎn)相關(guān)聯(lián)。2)不會(huì)使入選邊形成回路，除非入選邊的個(gè)數(shù)已等于圖中的頂點(diǎn)總數(shù)。在滿足以上兩點(diǎn)的候選邊中，挑選最短的邊作為入選邊。如此做下去，直到得到一個(gè)經(jīng)過(guò)所有頂點(diǎn)的回路。最后求得的回路是125341，代價(jià)是14。圖中最小代價(jià)的回路是12543一1，代價(jià)是10。這也是典型的貪心策略。,7.2.5貪心法,貪心法主要有以下兩個(gè)特點(diǎn)：（1）貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴(lài)于已做出的選擇，但不依賴(lài)于未作出的選擇。（2）最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。,7.2.6動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代美國(guó)數(shù)學(xué)家貝爾曼（RechardBellman）等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)性原理，把多階段決策過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題逐個(gè)求解，創(chuàng)立了解決多階段過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃,7.2.6動(dòng)態(tài)規(guī)劃,例如，要生產(chǎn)一批雪糕。在這個(gè)過(guò)程中要分好多環(huán)節(jié)。購(gòu)買(mǎi)牛奶，對(duì)牛奶提純處理，放入工廠加工，加工后的商品要包裝，包裝后就去銷(xiāo)售這樣各個(gè)環(huán)節(jié)就可以看做是一個(gè)階段，產(chǎn)品在不同的時(shí)候有不同的狀態(tài)剛開(kāi)始時(shí)只是白白的牛奶，進(jìn)入生產(chǎn)后做成了各種造型，從冷凍庫(kù)拿出來(lái)后就變成雪糕，由液態(tài)變成固態(tài)。每個(gè)形態(tài)就是一個(gè)狀態(tài)，那從液態(tài)變成固態(tài)經(jīng)過(guò)了冰凍這一操作，這個(gè)操作就是一個(gè)決策。一個(gè)狀態(tài)經(jīng)過(guò)一個(gè)決策變成了另外一個(gè)狀態(tài)，這個(gè)過(guò)程就是狀態(tài)轉(zhuǎn)移，用來(lái)描述狀態(tài)轉(zhuǎn)移的方程就是狀態(tài)轉(zhuǎn)移方程。這就是所謂的動(dòng)態(tài)規(guī)劃。,7.2.6動(dòng)態(tài)規(guī)劃,多階段決策問(wèn)題，人們很容易舉出下面這個(gè)例子。多段圖中的最短路徑問(wèn)題：在下圖中找出從A1到D1的最短路徑。仔細(xì)觀察這個(gè)圖不難發(fā)現(xiàn)，它有一個(gè)特點(diǎn)。我們將圖中的點(diǎn)分為四類(lèi)（圖中的A、B、C、D），那么圖中所有的邊都處于相鄰的兩類(lèi)點(diǎn)之間，并且都從前一類(lèi)點(diǎn)指向后一類(lèi)點(diǎn)。這樣，圖中的邊就被分成了三類(lèi)（AB、BC、CD）。我們需要從每一類(lèi)中選出一條邊來(lái)，組成從A1到D1的一條路徑，并且這條路徑是所有這樣的路徑中的最短者。,7.2.6動(dòng)態(tài)規(guī)劃,多階段決策問(wèn)題的最優(yōu)化求解目標(biāo)是獲取導(dǎo)致問(wèn)題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到最優(yōu)解。動(dòng)態(tài)規(guī)劃思想實(shí)質(zhì)是分治思想和冗余解決方法的結(jié)合。動(dòng)態(tài)規(guī)劃過(guò)程是：每次決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出