TSP-动态规划_精品文档.pptVIP

动态规划算法总体思想:在每种情况下,列出各种可能的局部解,然后按某些条件,从局部解（或中间解）中挑选出可能产生最佳解的结果，而扬弃其余。从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。分析:令T(Vi;V)表示从Vi出发,经V各点一次,最后返回Vi的路径模型T(Vi;V)=min{dij+T(Vj;V\{vj})}要求的问题是:T(v1;{v2,v3,v4})从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。(1)T(V2;φ)=6T(v3;φ)=7T(v4;φ)=9(2)T(V2;V3)=d23+T(V3;φ)=6+7=13T(V2;V4)=d24+T(V4;φ)=5+9=14T(V3;V2)=d32+T(V2;φ)=6+6=12T(V3;V4)=d34+T(V4;φ)=8+9=17T(V4;V2)=d42+T(V2;φ)=5+6=11T(V4;V3)=d43+T(V3;φ)=8+7=15从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。(2)T(V2;V3)=13T(V2;V4)=14T(V3;V2)=12T(V3;V4)=17T(V4;V2)=11T(V4;V3)=15(3)T(V2;V3,V4)=min{d23+T(V3;V4),d24+T(V4;V3)}=min{6+17,5+15}=20T(V3;V2,V4)=min{d32+T(V2;V4),d34+T(V4;V2)}=min{6+14,8+11}=19T(V4;V2,V3)=min{d42+T(V2;V3),d43+T(V3;V2)}=min{5+13,8+12}=18从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。(3)T(V2;V3,V4)=20T(V3;V2,V4)=19T(V4;V2,V3)=18(4)T(V1;V2,V3,V4)=min{d12+T(V2;V3,V4),d13+T(V3;V2,V4),d14+T(V4;V2,V3)}=min{6+20,7+19,9+18}=26故最短路径为：1,2,4,3,11,3,4,2,1结论:动态规划虽然提供了一种解法，但也不是一种可行的算法。最佳原理:假设为了解决某一优化问题，需要依次作出n个决策D1,D2,…,Dn，如若这个决策是最优的，对于任何一个整数k，1kn，不论前面k个是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策DK+1,Dk+2,…,Dn也是当前最优的。*算法总体思想TSP问题多段递推公式TSP问题TSP问题TSP问题TSP问题T(V1;V2,V3,V4)T(V2;V3,V4)T(V3;V2,V4)T(V4;V2,V3)T(V4;V2)T(V4;V3)T(V2;V3)T(V2;V4)T(V3;V2)T(V3;V4)T(V2;φ)T(V2;φ)T(v3;φ)T(v3;φ)T(v4;φ)T(v4;φ)复杂性估计：算法总体思想算法总体思想