算法設(shè)計方案問答題整理

1、一、問答題(30分)。什么是最壞情況時間復(fù)雜性？什么是平均情況時間復(fù)雜性？什么是遞歸算法？什么是遞歸函數(shù)？遞歸算法:直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸函數(shù):用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)的二要素是什么？邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限 次計算后得出結(jié)果。分治法的設(shè)計思想是什么？分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以 便各個擊破，分而治之什么叫問題的最優(yōu)子結(jié)構(gòu)性質(zhì)？矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算

2、法求解的顯著特征動態(tài)規(guī)劃基本步驟是什么？找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征遞歸地定義最優(yōu)值以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解動態(tài)規(guī)劃算法的基本要素是什么？舉例說明一些可以用動態(tài)規(guī)劃算法解決的問題。說明分治法與動態(tài)規(guī)劃法的相同點和不同之處？貪心算法的兩個重要要素是什么？舉例說明一些可以用貪心算法解決的問題。貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問 題的最優(yōu)解。public static float loading(float c, float w, int x)int n=w.length。El

3、ement d = new Element nofor (int i = 0。 i n。 i+)di = new Element(wi,i)。MergeSort.mergeSort(d)。float opt=0。for (int i = 0。i n。i+) xi = 0。for (int i = 0。i n & di.w = c。i+) xdi.i = 1。opt+=di.w。c -= di.w。return opt。什么叫貪心選擇性質(zhì)？所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇 來達(dá)到貪心算法與動態(tài)規(guī)劃算法的的相同點和不同之處？貪心算法和動態(tài)規(guī)劃算法都要

4、求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。背包問題與0-1背包問題有何區(qū)別？0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi,背包的容量 為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i 的一部分，而不一定要全部裝入背包，IWiWn。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背 包問題卻不能用貪心算法求解。用貪心算法解背包問題的基本步驟：首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單 位重量價值最

5、高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超 過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去， 直到背包裝滿為止。具體算法可描述如下頁：public static float knapsack(float c,float w, float v,float x)int n=v.length。Element d = new Element n。for (int i = 0。 i n。 i+) di = new Element(wi,vi,i)。MergeSort.mergeSort(d)。int iofloat opt=0ofor (i=0o

6、 in。i+) xi=0。for (i=0o ic) breakoxdi.i=1。opt+=di.v。c-=di.w。if (in)(xdi.i=c/di.w。opt+=xdi.i*di.v。return opt。對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終 能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1 背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。 由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題?；厮莘ㄅc分支限界法之間的相同點是什么？不同之處在哪些方面？分支限界法基本思想是什么？分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點?；罱Y(jié)點一旦成為擴(kuò)展結(jié)點， 就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié) 點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程 一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。常用的剪枝函數(shù)有哪兩類？約束函數(shù)的功能是什么？限