動態(tài)規(guī)劃及貪心選擇實驗

《動態(tài)規(guī)劃及貪心選擇實驗》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、實驗報告實驗內容：姓名：魏成林學號：201101020126班級：計算機科學與技術完成日期：2013-11-7實驗要求一、實驗目的1.了解動態(tài)規(guī)劃和貪心選擇算法2.區(qū)分兩個算法二、實驗內容1.實現矩陣連乘、0-1背包問題、最優(yōu)搜索樹三個問題的動態(tài)規(guī)劃算法。2．實現活動安排的貪心算法。3.對動態(tài)規(guī)劃和貪心算法進行比較。實驗報告一、實驗問題回答1.概述動態(tài)規(guī)劃算法思想。答：將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。保存已解決的子問題的答案，在需要的時候再找出來

2、避免重復計算，從而得到算法。2.滿足什么條件的問題可以用動態(tài)規(guī)劃算法求解。答：具有最優(yōu)子結構和子問題重疊性質。3.寫出動態(tài)規(guī)劃算法求解的步驟。答：(1)找出最優(yōu)解的性質，并刻畫其結構特征；(2)遞歸的定義最優(yōu)值；(3)以自底向上的方式計算出最優(yōu)值；(4)根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。1.什么是最優(yōu)子結構，如何證明一個問題有最優(yōu)子結構性質。答：問題的最優(yōu)解包含著其子問題的最優(yōu)解；利用反證法來證明一個問題有最優(yōu)子結構性質，假設一個問題不具有最優(yōu)子結構性質，然后逐步的證明該問題存在最優(yōu)子結構

3、性質，與假設的產生矛盾，假設不成立，所以該問題就有最優(yōu)子結構。2.寫出貪心算法思想。答：貪心算法并不從整體最優(yōu)考慮，而是作出在某種局部意義上的最優(yōu)選擇。3.貪心算法的基本要素是什么？答：具有最優(yōu)子結構性質和貪心選擇性質。4.0-1背包問題可否用貪心算法求解？不可以是為什么？如果可以請用貪心算法實現，并與動態(tài)規(guī)劃算法實現的0-1背包問題求解結果對比，是否正確。答：0-1背包問題不能用貪心算法求解。因為在某種情況下，不能保證背包被裝滿，也就是說背包有剩余的空間沒有利用起來，導致無法達到最大價值。5.

4、分治策略和動態(tài)規(guī)劃的異同。答：分治策略得到的子問題往往是獨立的，而動態(tài)規(guī)劃得到的子問題不是獨立的。分治法得到的子問題太多導致耗費時間，而且存在許多的重復計算。動態(tài)規(guī)劃則可以避免重復計算。6.動態(tài)規(guī)劃和貪心選擇的異同。答：共同點是兩種算法都需要問題具有最優(yōu)子結構。不同的是有些問題可以用貪心算法求解，而有些問題不能用貪心算法求解。二、實驗總結與收獲用幾句簡短的話對實驗進行總結，并寫出自己的心得和收獲。每一項都用幾個小點表示。如：本次實驗收獲如下：1.。。。。。。2.。。。。。。