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

1、.算法分析與設(shè)計學習中心： 專 業(yè)： 學 號： 姓 名： 作業(yè)練習二一、名詞解釋1、MST性質(zhì)2、子問題的重疊性質(zhì)遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。二、簡答題1、簡述動態(tài)規(guī)劃算法求解的基本要素。答：動態(tài)規(guī)劃算法求解的基本要素包括：1)最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提；2)動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果，即重疊子問題。2、備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。答：備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，

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

3、解的關(guān)鍵特征。三、算法編寫及算法應(yīng)用分析題1、設(shè)計求解如下最大子段和問題的動態(tài)規(guī)劃算法。只需給出其遞推計算公式即可。最大子段和問題：給定由n 個整數(shù)（可能為負整數(shù)）組成的序列a1a2 an，求該序列形如ikj ak的子段和的最大值。當所有整數(shù)均為負整數(shù)時定義其最大子段和為0。依次定義，所求的最優(yōu)值為max0, max1ijn ikj ak 。2、關(guān)于多段圖問題。設(shè)G(V，E)是一個賦權(quán)有向圖，其頂點集V被劃分成k2個不相交的子集Vi：，其中，V1和Vk分別只有一個頂點s（稱為源）和一個頂點t（稱為匯），圖中所有的邊（u,v），。求由s到t的最小成本路徑。 給出使用動態(tài)規(guī)劃算法求解多段圖問題的基

4、本思想。 使用上述方法求解如下多段圖問題。3、最優(yōu)二元歸并問題：已知將兩個分別包含 a 個和b 個記錄的已分類文件歸并在一起得到一個分類文件需作a+b 次記錄移動。現(xiàn)有n 個已分類文件F1,F1,Fn，它們的記錄個數(shù)分別為l1, l2, ln。現(xiàn)在考慮使用二元歸并模式將這n 個文件歸并成一個分類文件，要求記錄移動次數(shù)最少。設(shè)計一個貪心算法來求解一種最優(yōu)的二元歸并（即記錄移動次數(shù)最少的二元歸并）。4、帶限期的作業(yè)調(diào)度問題：n 個作業(yè)需要在一臺機器上處理，每個作業(yè)可在單位時間內(nèi)完成。每個作業(yè)i 都有一個截止期限di0(di 為整數(shù))，當且僅當作業(yè)i 在它的截止期限之前被完成，獲得pi0 的效益。一種可行的調(diào)度方案為n 個作業(yè)的一個子集J，其中J 中的每個作業(yè)都能