算法分析與設(shè)計(jì)考前復(fù)習(xí)重點(diǎn)

1、個(gè)特性，程序與算法的算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，滿(mǎn)足性質(zhì)：輸入：有外部提供的量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令是清晰，無(wú)歧義的。有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿(mǎn)足算法的性質(zhì)(4)有限性。2算法分析是對(duì)算法所需要的兩種計(jì)算機(jī)資源一時(shí)間和空間進(jìn)行估算。3何謂遞歸？構(gòu)成遞歸需具備的2個(gè)條件(要素)。遞歸(recursion)是數(shù)學(xué)與計(jì)算機(jī)科學(xué)中的基本概念。直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱(chēng)為遞歸函數(shù)

2、。構(gòu)成遞歸需具備的條件：不能無(wú)限制地調(diào)用本身，須有個(gè)出口，化簡(jiǎn)為非遞歸狀況處理(邊界條件或遞歸出口)；子問(wèn)題與原問(wèn)題為同一類(lèi)型，且更為簡(jiǎn)單(遞歸模式或遞歸體).4、遞歸算法與非遞歸算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便，是算法設(shè)計(jì)中的一種強(qiáng)有力的工具。缺點(diǎn)：遞歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時(shí)的輔助操作增多，因此，遞歸算法的運(yùn)行效率較低。因此無(wú)論是耗賽的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。5、利用分治法求解的問(wèn)題一般應(yīng)具有哪四個(gè)特征(即分治法的適用條件)。

3、該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有結(jié)構(gòu)自相似性質(zhì)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。6、求解背包問(wèn)題和0/1背包問(wèn)題的約束條件有什么不同？7、動(dòng)態(tài)規(guī)劃法和分治法之間有什么共同點(diǎn)？有什么不同點(diǎn)？動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余動(dòng)態(tài)規(guī)劃法與分治法類(lèi)似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并 通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。分治法中的各個(gè)子問(wèn)題是獨(dú)立的（即不包含公共的子問(wèn)題），因此一旦遞歸地求出各子 問(wèn)題的解后，便可自下而上地將子問(wèn)題的

4、解合并成問(wèn)題的解。不足之處：如果各子問(wèn)題 是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈 現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí) 加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。8、求解0/1背包問(wèn)題的三種貪心策略（1）選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選 擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè) 數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（2）選擇重量最輕的物品，因?yàn)檫@可以裝入

5、盡可能多的物品，從而增加背包的總價(jià)值。 但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒(méi)能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（3）選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。9、簡(jiǎn)述動(dòng)態(tài)規(guī)劃法和貪心法之間的異同。動(dòng)態(tài)規(guī)劃算法與貪心算法比較，其相同點(diǎn)是：?jiǎn)栴}都應(yīng)具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，都是將問(wèn)題 的求解過(guò)程化為多階段決策問(wèn)題。區(qū)別是:貪心法每采用一次貪心策略便做出唯一決策，求解過(guò) 程只產(chǎn)生一個(gè)決策序列;求解過(guò)程為自頂向下，不一定得到最優(yōu)解；動(dòng)態(tài)規(guī)劃的求解過(guò)程產(chǎn)生多 個(gè)決策序列，下一步的選擇總是依賴(lài)上一步的結(jié)果，求解過(guò)程多為自底向上，總能得到最優(yōu)

6、解。動(dòng)態(tài)規(guī)劃法通常以自底向上的方式求解各個(gè)子問(wèn)題，而貪心法則通常以自頂向下的方式做出 一系列的貪心選擇。10、什么是最優(yōu)子結(jié)構(gòu)性質(zhì)？動(dòng)態(tài)規(guī)劃法如何利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)求解問(wèn)題的最優(yōu)解？（利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出 整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。）當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱(chēng)此問(wèn)題 滿(mǎn)足最優(yōu)性原理。11、用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題應(yīng)具有哪兩個(gè)特征？1）滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì)，即該問(wèn)題的最優(yōu)解中也包含著其子問(wèn)題的最優(yōu)解。2）待求解問(wèn)題分解成若干個(gè)相互重疊的子問(wèn)題12、利用貪心法

7、求解的問(wèn)題具有的兩個(gè)特征。（1）最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱(chēng)此問(wèn)題滿(mǎn)足最優(yōu)性原理。（2）貪心選擇性質(zhì)：所謂貪心選擇性質(zhì)是指問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選 擇，即貪心選擇來(lái)得到。13、用回溯算法解決問(wèn)題的時(shí)候一般步驟。1、定義一個(gè)解空間，它包含問(wèn)題的解。2、利用適于搜索的方法組織解空間。3、利用深度優(yōu)先法搜索解空間。4、利用剪枝函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。14、回溯法對(duì)解空間樹(shù)的搜索過(guò)程中，采用的兩種策略避免無(wú)效搜索。(1)用約束條件剪去得不到可行解的子樹(shù);(2)用目標(biāo)函數(shù)剪去得不到最優(yōu)解的子樹(shù)。15、簡(jiǎn)述利用回溯

8、法對(duì)解空間樹(shù)的搜索過(guò)程。回溯法從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略遍歷解空間樹(shù)，搜索滿(mǎn)足約束條件的解。在搜索至 樹(shù)中任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)對(duì)應(yīng)的部分解是否滿(mǎn)足約束條件，或者是否超出目標(biāo)函數(shù)的 界，也就是判斷該結(jié)點(diǎn)是否包含問(wèn)題的(最優(yōu))解，如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為 根的子樹(shù)的搜索，即所謂剪枝(Pruning);否則，進(jìn)入以該結(jié)點(diǎn)為根的子樹(shù)，繼續(xù)按照深度 優(yōu)先策略搜索。16、回溯法求解問(wèn)題時(shí)，常常遇到兩種典型的解空間樹(shù)，在用回溯法求解問(wèn)題時(shí)，常常遇到兩種典型的解空間樹(shù):(1)子集樹(shù)(SubsetTrees):當(dāng)所給問(wèn)題是從n個(gè)元素的集合中找出滿(mǎn)足某種性質(zhì)的子集 時(shí)，相應(yīng)的解空間樹(shù)稱(chēng)為子集樹(shù)。

9、在子集樹(shù)中，|S1| = |S2|=. = |Sn|=c，即每個(gè)結(jié)點(diǎn)有相同數(shù) 目的子樹(shù)，通常情況下c=2，所以，子集樹(shù)中共有2n個(gè)葉子結(jié)點(diǎn)，因此，遍歷子集樹(shù)需要。(2n)時(shí)間。(2 )排列樹(shù)(Permutation Trees):當(dāng)所給問(wèn)題是確定n個(gè)元素滿(mǎn)足某種性質(zhì)的排列時(shí)， 相應(yīng)的解空間樹(shù)稱(chēng)為排列樹(shù)。在排列樹(shù)中，通常情況下，|S1| = n , |S2| = n-1，|Sn| = 1 , 所以，排列樹(shù)中共有n!個(gè)葉子結(jié)點(diǎn)，因此，遍歷排列樹(shù)需要Q (n!)時(shí)間。17,寫(xiě)出n=4時(shí)0-1背包問(wèn)題的解空間。18、分治法：求解遞歸方程；動(dòng)態(tài)規(guī)劃：0-1背包問(wèn)題和TSP問(wèn)題填表；貪心法：（1 ）三種

10、貪心策略求解0-1皆包問(wèn)題；（2）TSP問(wèn)題的最近鄰點(diǎn)貪心策略；（3 ）求最小生成樹(shù)最近頂 點(diǎn)貪心策略；回溯法：0-1背包問(wèn)題和TSP問(wèn)題的解空間樹(shù)或搜索空間樹(shù)?；厮莘?1背包問(wèn)題搜索樹(shù)例如，對(duì)于n=3的0/1背包問(wèn)題，三個(gè)物品的重量 為20, 15, 10，價(jià)值為20, 30, 25，背包容量為 25，從圖所示的解空間樹(shù)的根結(jié)點(diǎn)開(kāi)始搜索，搜 索過(guò)程如下：不可行解價(jià)值=20 價(jià)值=55價(jià)值=30價(jià)值=25 價(jià)值=0回溯法tsp問(wèn)題搜索樹(shù)83671282886823768貪心法最近鄰點(diǎn)貪心策略求tsp問(wèn)題(1)最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇最近的一 個(gè)，直到經(jīng)過(guò)了所有的

11、城市，最后回到出發(fā)城市。83 3 2 6387 3 23782 523 28362 5 38(a) 5城市的代價(jià)矩陣C=(b)城市1 城市4(c)城市4-城市3(d)城市3 -城市5(e) 城市5 -城市2(f) 城市2 -城市1最近鄰點(diǎn)貪心策略求解TSP問(wèn)題的過(guò)程最近頂點(diǎn)策略：任選一個(gè)頂點(diǎn)，并以此建立起生成樹(shù)，每一步的貪心選擇是簡(jiǎn) 單地把不在生成樹(shù)中的最近頂點(diǎn)添加到生成樹(shù)中。(a)連通網(wǎng)，U= A cost=( A, B )34,( A, C )46, (A, D)8 ,(A, E)8 ,(A, F)19 (b)U=( A, Fcost=( A, B )34, (F, C)25 ,F, D)

12、25,( F, E)26(U = A, F, C, D cost=( A, B )34, (F, E)26 U= A, F, C, D, E cost=(E, B )12 U= A, F, C, D, E, B cost= Prim算法構(gòu)造最小生成樹(shù)的過(guò)程示意注：cost表示候選最短邊集0-1背包問(wèn)題例如，有3個(gè)物品，其重量分別是20, 30, 10，價(jià)值分別為60,120, 50，背包的容量為50，應(yīng)用三種貪心策略裝入背包的物品和獲得的價(jià)值如圖所示。10/2030TU(a)三個(gè)物品及背包(b)貪心策略 1(c)貪心策略2 (d)貪心策略 3動(dòng)態(tài)規(guī)劃tsp問(wèn)題動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題的填表過(guò)程

13、假設(shè)n個(gè)頂點(diǎn)用0n-1的數(shù)字編號(hào)，首先生成1n-1個(gè)元素的子集存放在數(shù)組V2 n-1 中，設(shè)數(shù)組 dn2 n-1存放迭代結(jié)果，其中dij表示從頂點(diǎn)i經(jīng)過(guò)子集 Vj中的頂點(diǎn)一次且僅一次，最 后回到出發(fā)點(diǎn) 0的最短路徑長(zhǎng)度。（從頂點(diǎn)0出發(fā)） 1231, 21, 32, 31, 2, 30101586726951033121114廠83 6 782 34 823 7 58帶權(quán)圖的代價(jià)矩陣240-1背包問(wèn)題例如，有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè) (n+1) X (C+1)的二維表V，Vij 表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。01