tsp問題之動態(tài)規(guī)劃法(文件)
【正文】 ]=min(c[i][k]+d[k][j1])。 特點(diǎn) ：最優(yōu)子結(jié)構(gòu)、自底向遞歸、子問題相互重疊。 ?一般來說，如果所求解問題對于最優(yōu)性原理成立，則說明用動態(tài)規(guī)劃方法有可能解決該問題。路徑上的每一步都只能往左下或右下走。 動態(tài)規(guī)劃法（三） ? 動態(tài)規(guī)劃法步驟 （ 1）分段：將原問題分解為若干個相互重疊的子問題； （ 2）分析：分析問題是否滿足最優(yōu)性原理，找出動態(tài)規(guī)劃函數(shù)的遞推式； （ 3）求解：利用遞推式自底向上計算，實(shí)現(xiàn)動態(tài)規(guī)劃過程。 ?無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。 4． 輸出最短路徑長度 d[0][2n11]。 j++) for (i=1。 in。TSP問題之動態(tài)規(guī)劃法 提綱 ? 什么是 TSP問題 ? 一般的解決辦法 ——窮舉法 ? 動態(tài)的解決辦法 ? 什么是動態(tài)規(guī)劃法 ? 使用動態(tài)規(guī)劃法的條件 ? 動態(tài)規(guī)劃法解決常見問題 TSP問題 TSP問題的描述： 旅行家要旅行 n個城市，要求經(jīng)歷各個城市且僅經(jīng)歷一次，然后回到出發(fā)城市，并要求所走的路程最短。) d(k， { }) ＝ Cik (k≠i) 其中，Ｃ ik表示 i?k的距離 0 1 3 2 3 6 6 7 5 3 7 2 4 3 2 5 從城市 0出發(fā)，經(jīng)城市 3然后回到城市 0的最短路徑長度是： d(0, {1, 2, 3})=min{ C01+ d(1, { 2, 3}), C
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1