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

1、算法分析與設(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)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提；2) 動態(tài)規(guī)劃算法， 對每一個子問題只解一次， 而后將其解保存在一個表格中， 當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果，即重疊子問題。2、備忘錄方法和動態(tài)規(guī)劃算法相比有何異同簡述之。答： 備忘錄方法是動態(tài)規(guī)劃算法的變形。 與

2、動態(tài)規(guī)劃算法一樣， 備忘錄方法用表格保存已解 決的子問題的答案， 在下次需要解此問題時， 只要簡單地查看該子問題的解答， 而不必重新 計算。 備忘錄方法與動態(tài)規(guī)劃算法不同的是， 備忘錄方法的遞歸方式是自頂向下的， 而動態(tài) 規(guī)劃算法則是自底向上遞歸的。 因此， 備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相 同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看， 避免了相同的 子問題的重復(fù)求解，而直接遞歸方法沒有此功能。3、貪心算法求解的問題主要具有哪些性質(zhì)簡述之。答：貪心算法求解的問題一般具有二個重要的性質(zhì)：一是貪心選擇性質(zhì)，這是貪心算法可行的第一個基本要素；另一個是最優(yōu)子結(jié)構(gòu)性

3、質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。三、算法編寫及算法應(yīng)用分析題 1、設(shè)計求解如下最大子段和問題的動態(tài)規(guī)劃算法。只需給出其遞推計算公式即可。最大子段和問題：給定由 n個整數(shù)（可能為負整數(shù)）組成的序列 a1a2an,求該序列形如i < kw j ak的子段和的最大值。當(dāng)所有整數(shù)均為負整數(shù)時定義其最大子段和為0。依次定義，所求的最優(yōu)值為 max0, maxi w i w j w n X i w kw j ak 。k>2個不相交t （稱為匯），2、關(guān)于多段圖問題。設(shè) 8 （V , E）是一個賦權(quán)有向圖，其頂點集 V被劃分成 的子集V : 1 i k，其中，Vi和V

4、分別只有一個頂點s （稱為源）和一個頂點 圖中所有的邊（u,v），u Vi，v Vi i。求由s到t的最小成本路徑。 給出使用動態(tài)規(guī)劃算法求解多段圖問題的基本思想。使用上述方法求解如下多段圖問題。ViV2V3V4V53、最優(yōu)二元歸并問題： 已知將兩個分別包含 a 個和 b 個記錄的已分類文件歸并在一起得到一個分類文件需作 a+b次記錄移動?，F(xiàn)有n個已分類文件F1,F1,?,Fn,它們的記錄個數(shù)分別 為l 1, 12, ?, In?，F(xiàn)在考慮使用二元歸并模式將這n個文件歸并成一個分類文件，要求記錄移動次數(shù)最少。 設(shè)計一個貪心算法來求解一種最優(yōu)的二元歸并 （即記錄移動次數(shù)最少的二元 歸并）。4、帶限期的作業(yè)調(diào)度問題： n 個作業(yè)需要在一臺機器上處理,每個作業(yè)可在單位時間內(nèi)完 成。每個作業(yè) i 都有一個截止期限 di >0（di 為整數(shù) ） ，當(dāng)且僅當(dāng)作業(yè) i 在它的截止期限之前 被完成，獲得pi>0的效益。一種可行的調(diào)度方案為 n個作業(yè)的一個子集J，其中J中的每個 作