動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問(wèn)題算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-展示頁(yè)
2025-07-31 09:46本頁(yè)面
【正文】 r）+COST（r）取最小值COST（j） c（j，r）+COST（r）。E是邊集，c（i，j）是邊i，j的成本。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。1） 找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）；3） 以自底向上的方式計(jì)算出最優(yōu)值；4） 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。即當(dāng)前最優(yōu)只與上一步有關(guān)。子問(wèn)題重疊性質(zhì)：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。對(duì)于一個(gè)多階段過(guò)程問(wèn)題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動(dòng)態(tài)規(guī)劃的方法，還要看該問(wèn)題的子問(wèn)題是否具有重疊性質(zhì)。這類問(wèn)題的解決是多階段的決策過(guò)程。算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問(wèn)題 評(píng)分 實(shí)驗(yàn)日期 年 月 日 指導(dǎo)教師 姓名 專業(yè)班級(jí) 學(xué)號(hào) 1. 理解最優(yōu)子結(jié)構(gòu)的問(wèn)題。有一類問(wèn)題的活動(dòng)過(guò)程可以分成若干個(gè)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1