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

1、算法分析與設(shè)計(jì)學(xué)習(xí)中心： 專 業(yè)： 學(xué) 號： 姓 名： 作業(yè)練習(xí)二一、名詞解釋1、MST性質(zhì)2、子問題的重疊性質(zhì)遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次，這種性質(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í)，只是簡單地用常數(shù)時(shí)間查看一下結(jié)果，即重疊子問題。2、備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。答：備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，備

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

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

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