算法設(shè)計(jì)方案問(wèn)答題整理

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

2、法求解的顯著特征動(dòng)態(tài)規(guī)劃基本步驟是什么？找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征遞歸地定義最優(yōu)值以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解動(dòng)態(tài)規(guī)劃算法的基本要素是什么？舉例說(shuō)明一些可以用動(dòng)態(tài)規(guī)劃算法解決的問(wèn)題。說(shuō)明分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)和不同之處？貪心算法的兩個(gè)重要要素是什么？舉例說(shuō)明一些可以用貪心算法解決的問(wèn)題。貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn) 題的最優(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ì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇 來(lái)達(dá)到貪心算法與動(dòng)態(tài)規(guī)劃算法的的相同點(diǎn)和不同之處？貪心算法和動(dòng)態(tài)規(guī)劃算法都要

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

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