TSP问题之动态规划法.ppt

《TSP问题之动态规划法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、TSP问题之动态规划法提纲什么是TSP问题一般的解决办法——穷举法动态的解决办法什么是动态规划法使用动态规划法的条件动态规划法解决常见问题TSP问题TSP问题的描述：旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。0132366753726325TSP问题——穷举法解决abdc235187序号路径路径长度是否最短１a->b->c->d->a18否２a->b->d->c->a11是３a>c->b->d->a23否４a->c->d->b->a11是５a->d->b->c->a23否６a->d->c->b->a18否TSP问题——动态规划假

2、设找出的一条最短的回路：S0S1S2S3S0我们可以利用结论：“S1S2S3S0“必然是从S1到S0通过其它各点的一条最短路径。（如果不是，则会出现矛盾）S0S1S3S2Length(总回路)=Length(S0S1)+Length(S1S2S3S0)可以把问题简化：把求通过各点的一条最短的回路求解从某个（任意）确定点到回路中最后一个点的最短路径TSP问题——动态规划从上面的公式把总回路长度分解：Length(回路)=Min{Length(01)+Length(1…0)，Length(02)+Length(2…0)，Length(03)+L

3、ength(3…0)}规范化地表达上面的公式d(i，V)表示从i点经过点集Ｖ各点一次之后回到出发点的最短距离d(i，V‘)＝min{Cik+d(k,V－{k})}(k∈V')d(k，{})＝Cik(k≠i)其中，Ｃik表示ik的距离0132366753724325从城市0出发，经城市1、2、3然后回到城市0的最短路径长度是：d(0,{1,2,3})=min{C01+d(1,{2,3}),C02+d(2,{1,3}),C03+d(3,{1,2})}这是最后一个阶段的决策，它必须依据d(1,{2,3})、d(2,{1,3})和d(3,{1,2})的计算结果，而：d(1,{2,

4、3})=min{C12+d(2,{3}),C13+d(3,{2})}d(2,{1,3})=min{C21+d(1,{3}),C23+d(3,{1})}d(3,{1,2})=min{C31+d(1,{2}),C32+d(2,{1})}继续写下去：d(1,{2})=C12+d(2,{})d(2,{3})=C23+d(3,{})d(3,{2})=C32+d(2,{})d(1,{3})=C13+d(3,{})d(2,{1})=C21+d(1,{})d(3,{1})=C31+d(1,{})C02+d(2,{1,3})C01+d(1,{2,3})C03+d(3,{1,2})d(0,{1,2

5、,3})C12+d(2,{3})C13+d(3,{2})C21+d(1,{3})C23+d(3,{1})C31+d(1,{2})C32+d(2,{1})C23+d(3,{})C32+d(2,{})C13+d(3,{})C31+d(1,{})C12+d(2,{})C21+d(1,{})C30C20C10思考：这个过程，让人联想到什么？理解原理之后，先手动地在表格中把结果写出来，结果如下：ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114从伪代码中可以看出，我们应当继续解决以下问题：如何表示伪代码中集合Ｖ[j]呢?如何

6、产生这样的一个集合Ｖ[j]?TSP问题1．for(i=1;i

7、二进制表示数字123７023６013５012４003３002２001１000０集合表示序号集合的表示模型动态规划法（一）动态规划法：定义：将每个子问题只求解一次，并将其解保存在一个表格中，当需要再次求解此子问题时，只是简单地通过查表获得该子问题的解，从而避免了大量的重复计算。特点：最优子结构、自底向递归、子问题相互重叠。动态规划法使用的条件：问题符合最优性原理动态规划法（二）最优性原理：对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态