tsp問(wèn)題之動(dòng)態(tài)規(guī)劃法-wenkub
2022-08-22 20:35:20 本頁(yè)面
【正文】 3 5 1 8 7 序號(hào) 路徑 路徑長(zhǎng)度 是否最短 １ abcda 18 否 ２ abdca 11 是 ３ acbda 23 否 ４ acdba 11 是 ５ adbca 23 否 ６ adcba 18 否 TSP問(wèn)題 —— 動(dòng)態(tài)規(guī)劃 假設(shè)找出的一條最短的回路： S0?S1?S2 ? S3?S0 我們可以利用結(jié)論： “ S1?S2 ? S3?S0 “必然是從 S1 到 S0通過(guò)其它各點(diǎn)的一條最短路徑。（如果不是，則會(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) } ?規(guī)范化地表達(dá)上面的公式 d(i， V) 表示從 i點(diǎn)經(jīng)過(guò)點(diǎn)集Ｖ各點(diǎn)一次之后回到出發(fā)點(diǎn)的最短距離 d(i， V‘) ＝ min {Cik+d(k,V－ {k})} (k∈ V39。 2． for (j=1。 i++) //依次進(jìn)行第 i次迭代 if (子集 V[j]中不包含 i) 對(duì) V[j]中的每個(gè)元素 k， 計(jì)算 d[i][j
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1