動(dòng)態(tài)規(guī)劃及貪心選擇實(shí)驗(yàn)

《動(dòng)態(tài)規(guī)劃及貪心選擇實(shí)驗(yàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

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

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

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