貨郎擔(dān)(旅行售貨商)動(dòng)態(tài)規(guī)劃

《貨郎擔(dān)(旅行售貨商)動(dòng)態(tài)規(guī)劃》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、一，問(wèn)題由來(lái)????貨郎擔(dān)問(wèn)題也叫旅行商問(wèn)題，即TSP問(wèn)題（TravelingSalesmanProblem），是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一?！??二，問(wèn)題描述????1）貨郎擔(dān)問(wèn)題提法：有n個(gè)城市，用1，2，…，n表示，城i,j之間的距離為dij，有一個(gè)貨郎從城1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短？　　　????2）旅行商問(wèn)題的提法：假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。三，問(wèn)題求解?　　1）動(dòng)態(tài)規(guī)劃解　　

2、　　?例題：?設(shè)v1，v2，……..，vn是已知的n個(gè)城鎮(zhèn)，城鎮(zhèn)vi到城鎮(zhèn)vj的距離為dij，現(xiàn)求從v1出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次返回v1的最短路程。?????分析：設(shè)S表示從v1到vi中間所可能經(jīng)過(guò)的城市集合，S實(shí)際上是包含除v1和vi兩個(gè)點(diǎn)之外的其余點(diǎn)的集合，但S中的點(diǎn)的個(gè)數(shù)要隨階段數(shù)改變。?????建模：狀態(tài)變量（i，S）表示：從v1點(diǎn)出發(fā)，經(jīng)過(guò)S集合中所有點(diǎn)一次最后到達(dá)vi。???????????最優(yōu)指標(biāo)函數(shù)fk（i，S）為從v1出發(fā)，經(jīng)過(guò)S集合中所有點(diǎn)一次最后到達(dá)vi。???????????決策變量Pk（i，S）表示：從v1經(jīng)k個(gè)中間城鎮(zhèn)的S集合到vi城鎮(zhèn)的最短路線上鄰

3、接vi的前一個(gè)城鎮(zhèn)，則動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為：??????????????fk（i，S）=???min{??fk-1（j，S、{j}+dji}????j屬于S?????????????f0（i，空集）=d1i?（k=1，2，…,n-1,i=2,3,…n)?????求解：K=0???????????????f0(2,空集)=d12=6?????????????????f0(3,空集)=d13=7???????????????f0(4,空集)=d14=9???????????當(dāng)k=1時(shí):?從城市V1出發(fā),經(jīng)過(guò)1個(gè)城鎮(zhèn)到達(dá)Vi的最短距離為:f1(2,{3})=f0?(3,空)+d?3

4、2?=7+8=15f1(2,{4})=f0?(4,空)+d?42?=9+8=14f1(3,{2})=f0?(2,空)+d?23?=6+9=15f1(3,{4})=f0?(4,空)+d?43?=9+5=14f1(4,{2})=f0?(2,空)+d?24?=6+7=13f1(4,{3})=f0?(3,空)+d?34?=7+8=15??當(dāng)k=2時(shí),???????????從城市V1出發(fā),中間經(jīng)過(guò)2個(gè)城鎮(zhèn)到達(dá)Vi的最短距離.f2(2,{3,4})=min[f1(3,{4})+d32,???f1(4,{3})+d42]?=min[14+8,15+5]=20?????????P2(2,{3,4

5、})=4f2(3,{2,4})=min[14+9,13+5]=18?P2(3,{2,4})=4??????f2(4,{2,3})=min[15+7,15+8]=22P2(4,{2,3})=2??當(dāng)k=3時(shí):從城市V1出發(fā),中間經(jīng)過(guò)3個(gè)城鎮(zhèn)最終回到Vi的最短距離.?f3(1,{2,3,4})=min[f2(2,{3,4})+d?21,f2(3,{2,4})+d31,f2(4,{2,3})+d41]=min[20+8,18+5,22+6]=23????P3(1,{2,3,4})=3逆推回去,貨郎的最短路線是1?2?4?3?1,最短距離為23.四，源碼#include

6、>#includeusingnamespacestd;intn;intcost[20][20]={};booldone[20]={1};intstart=0;//從城市0開(kāi)始intimin(intnum,intcur){if(num==1)//遞歸調(diào)用的出口returncost[cur][start];//所有節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)，最后返回最后一個(gè)節(jié)點(diǎn)到起點(diǎn)的路徑intmincost=10000;for(inti=0;i

7、if(mincost<=cost[cur][i]+cost[i][start]){continue;//其作用為結(jié)束本次循環(huán)。即跳出循環(huán)體中下面尚未執(zhí)行的語(yǔ)句。區(qū)別于break}done[i]=1;//遞歸調(diào)用時(shí)，防止重復(fù)調(diào)用intvalue=cost[cur][i]+imin(num-1,i);if(mincost>value){mincost=value;}done[i]=0;//本次遞歸調(diào)用完畢，讓下次遞歸調(diào)用}}returnmincost;}intmain(){//cin