算法分析與設(shè)計線下作業(yè)二樣本

《算法分析與設(shè)計》學(xué)習(xí)中心：專業(yè)：學(xué)號：姓名：作業(yè)練習(xí)二一、名詞解釋1、MST性質(zhì)2、子問題重疊性質(zhì)遞歸算法求解問題時，每次產(chǎn)生子問題并不總是新問題，有些子問題被重復(fù)計算多次，這種性質(zhì)稱為子問題重疊性質(zhì)。二、簡答題1、簡述動態(tài)規(guī)劃算法求解基本要素。答：動態(tài)規(guī)劃算法求解基本要素涉及：1)最優(yōu)子構(gòu)造是問題能用動態(tài)規(guī)劃算法求解前提；2)動態(tài)規(guī)劃算法，對每一種子問題只解一次，而后將其解保存在一種表格中，當(dāng)再次需要解此子問題時，只是簡樸地用常數(shù)時間查看一下成果，即重疊子問題。2、備忘錄辦法和動態(tài)規(guī)劃算法相比有何異同？簡述之。答：備忘錄辦法是動態(tài)規(guī)劃算法變形。與動態(tài)規(guī)劃算法同樣，備忘錄辦法用表格保存已解決子問題答案，在下次需要解此問題時，只要簡樸地查看該子問題解答，而不必重新計算。備忘錄辦法與動態(tài)規(guī)劃算法不同是，備忘錄辦法遞歸方式是自頂向下，而動態(tài)規(guī)劃算法則是自底向上遞歸。因而，備忘錄辦法控制構(gòu)造與直接遞歸辦法控制構(gòu)造相似，區(qū)別在于備忘錄辦法為每個解過子問題建立了備忘錄以備需要時查看，避免了相似子問題重復(fù)求解，而直接遞歸辦法沒有此功能。3、貪心算法求解問題重要具備哪些性質(zhì)？簡述之。答：貪心算法求解問題普通具備二個重要性質(zhì)：一是貪心選取性質(zhì)，這是貪心算法可行第一種基本要素；另一種是最優(yōu)子構(gòu)造性質(zhì)，問題最優(yōu)子構(gòu)造性質(zhì)是該問題可用貪心算法求解核心特性。三、算法編寫及算法應(yīng)用分析題1、設(shè)計求解如下最大子段和問題動態(tài)規(guī)劃算法。只需給出其遞推計算公式即可。最大子段和問題：給定由n個整數(shù)（也許為負(fù)整數(shù)）構(gòu)成序列a1a2…an，求該序列形如Σi≤k≤jak子段和最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時定義其最大子段和為0。依次定義，所求最優(yōu)值為max{0，max1≤i≤j≤nΣi≤k≤jak}2、關(guān)于多段圖問題。設(shè)G＝(V，E)是一種賦權(quán)有向圖，其頂點集V被劃提成k>2個不相交子集Vi：，其中，V1和Vk分別只有一種頂點s（稱為源）和一種頂點t（稱為匯），圖中所有邊（u,v），，。求由s到t最小成本途徑。①給出使用動態(tài)規(guī)劃算法求解多段圖問題基本思想。使用上述辦法求解如下多段圖問題。3、最優(yōu)二元歸并問題：已知將兩個分別包括a個和b個記錄已分類文獻(xiàn)歸并在一起得到一種分類文獻(xiàn)需作a+b次記錄移動。既有n個已分類文獻(xiàn)F1,F1,?,Fn，它們記錄個數(shù)分別為l1，l2,?，ln。當(dāng)前考慮使用二元歸并模式將這n個文獻(xiàn)歸并成一種分類文獻(xiàn)，規(guī)定記錄移動次數(shù)至少。設(shè)計一種貪心算法來求解一種最優(yōu)二元歸并（即記錄移動次數(shù)至少二元歸并）。4、帶限期作業(yè)調(diào)度問題：n個作業(yè)需要在一臺機(jī)器上解決，每個作業(yè)可在單位時間內(nèi)完畢。每個作業(yè)i均有一種截止期限di>0(di為整數(shù))，當(dāng)且僅當(dāng)作業(yè)i在它截止期限之前被完畢，獲得pi>0效益。一種可行調(diào)度方案為n個作業(yè)一種子集J，其中J