[其它技巧]lecture_04動(dòng)態(tài)規(guī)劃-資料下載頁(yè)
2024-10-18 22:30本頁(yè)面
【正文】 動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行： 2021/11/10 34 （ 1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征。 （ 2）遞歸地定義最優(yōu)值。 （ 3）以 自底向上 的方式計(jì)算出最優(yōu)值。 （ 4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。 其中（ 1）－（ 3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（ 4）可以省去。若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（ 4）。此時(shí)，在步驟（ 3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（ 4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個(gè)最優(yōu)解。 基本步驟 2021/11/10 35 三、動(dòng)態(tài)規(guī)劃問(wèn)題的特征 動(dòng)態(tài)規(guī)劃算法的有效性依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)： 最優(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)題：在用遞歸算法自頂向下解問(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è)表格中，在以后盡可能多地利用這些子問(wèn)題的解。 2021/11/10 36 課后任務(wù)： 一、 DIY在線作業(yè) (4): 《 ACM程序設(shè)計(jì) 》 在線作業(yè)（ 4） —— 動(dòng)態(tài)規(guī)劃（第一部分） 二、常規(guī)練習(xí)（包含以上作業(yè)） ? 100 1466 、 ? 108 117 ? 208 115 1160 ? 105 106 205 2151 2021/11/10 37 下一講： 計(jì)算幾何 2021/11/10 38 Wele to HDOJ Thank You
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1