tsp問(wèn)題之動(dòng)態(tài)規(guī)劃法(更新版)
【正文】 規(guī)劃 假設(shè)找出的一條最短的回路： S0?S1?S2 ? S3?S0 我們可以利用結(jié)論： “ S1?S2 ? S3?S0 “必然是從 S1 到 S0通過(guò)其它各點(diǎn)的一條最短路徑。 2． for (j=1。 特點(diǎn) ：最優(yōu)子結(jié)構(gòu)、自底向遞歸、子問(wèn)題相互重疊。路徑上的每一步都只能往左下或右下走。 ?無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。 j++) for (i=1。TSP問(wèn)題之動(dòng)態(tài)規(guī)劃法 提綱 ? 什么是 TSP問(wèn)題 ? 一般的解決辦法 ——窮舉法 ? 動(dòng)態(tài)的解決辦法 ? 什么是動(dòng)態(tài)規(guī)劃法 ? 使用動(dòng)態(tài)規(guī)劃法的條件 ? 動(dòng)態(tài)規(guī)劃法解決常見(jiàn)問(wèn)題 TSP問(wèn)題 TSP問(wèn)題的描述： 旅行家要旅行 n個(gè)城市，要求經(jīng)歷各個(gè)城市且僅經(jīng)歷一次，然后回到出發(fā)城市，并要求所走的路程最短。 j2n11。 ? 動(dòng)態(tài)規(guī)劃法使用的條件：?jiǎn)栴}符合最優(yōu)性原理 動(dòng)態(tài)規(guī)劃法（二） ? 最優(yōu)性原理： 對(duì)于一個(gè)具有 n個(gè)輸入 的最優(yōu)化問(wèn)題，其求解過(guò)程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。只需要求出這個(gè)最大和即可，不必給出具體路徑 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 動(dòng)態(tài)規(guī)劃法解決的常用問(wèn)題（四） ? 近似串匹配問(wèn)題 ? 最長(zhǎng)公共子序列問(wèn)題 ? ０ /１背包問(wèn)題
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1