tsp問(wèn)題之動(dòng)態(tài)規(guī)劃法(參考版)
2025-07-28 20:35本頁(yè)面
【正文】 路徑上的每一步都只能往左下或右下走。 動(dòng)態(tài)規(guī)劃法（三） ? 動(dòng)態(tài)規(guī)劃法步驟 （ 1）分段：將原問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題； （ 2）分析：分析問(wèn)題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式； （ 3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。 ?一般來(lái)說(shuō)，如果所求解問(wèn)題對(duì)于最優(yōu)性原理成立，則說(shuō)明用動(dòng)態(tài)規(guī)劃方法有可能解決該問(wèn)題。 ?無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。 特點(diǎn) ：最優(yōu)子結(jié)構(gòu)、自底向遞歸、子問(wèn)題相互重疊。 4． 輸出最短路徑長(zhǎng)度 d[0][2n11]。 i++) //依次進(jìn)行第 i次迭代 if (子集 V[j]中不包含 i) 對(duì) V[j]中的每個(gè)元素 k， 計(jì)算 d[i][j]=min(c[i][k]+d[k][j1])。 j++) for (i=1。 2． for (j=1。 in。（如果不是，則會(huì)出現(xiàn)矛盾） S0 S1 S3 S2 Length(總回路 ) = Length(S0?S1) + Length(S1? S2 ? S3?S0) 可以把問(wèn)題簡(jiǎn)化： 把求通過(guò)各點(diǎn)的一條最短的回路 ? 求解從某個(gè)（任意）確定點(diǎn)到回路中最后一個(gè)點(diǎn)的最短路徑 TSP問(wèn)題 —— 動(dòng)態(tài)規(guī)劃 從上面的公式把總回路長(zhǎng)度分解： ?Length(回路 ) = Min{ Length(0?1) + Length(1?… ?0)， Length(0?2) + Length(2?… ?0)， Length(0?3) + Length(3?… ?0) }
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1