動(dòng)態(tài)規(guī)劃的基本要素

動(dòng)態(tài)規(guī)劃的基本要素如下：

　　1、最優(yōu)子結(jié)構(gòu)。當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的重要線索。在動(dòng)態(tài)規(guī)劃算法中，利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。

　　2、重疊子問(wèn)題?？捎脛?dòng)態(tài)規(guī)劃算法求解的問(wèn)題應(yīng)具備的另一個(gè)基本要素是子問(wèn)題的重疊性質(zhì)。在用遞歸算法自頂向下求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要此子問(wèn)題時(shí)，只要簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常，不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此，用動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com