动态规划：旅行售货员问题

例
20
1 2
15 35 25
4
10
3
12
解(2,3),(3,4),(1,2) ,(1,4)不是最优解，其开销为77。
shortestLinkTSP(V,E,W) R =E; C=∅; While R is not empty: Remove the lightest (shortest) edge, vw, from R. if vw does not make a cycle with edges in C and vw would not be the third edge incident on v or w. Add the edges connecting the endpoints of the path in C; return C;
旅行售货员问题
一、最近邻居策略
如同求一颗最小支撑树一样，使用 贪心算法的思想，但这里不求一颗树， 而要得到一个圈。
“最近邻居策略”算法 最近邻居策略”
nearestTSP(V,E,W) Select an arbitrary vertex s to start the cycle c. v = s; While there are vertices not yet in C: Select an edge vw of minimum weight, where w is not in C. Add edge vw to C; v = w; add the edges vs to C; return C;
“最近邻居策略”的复杂性 最近邻居策略”
最坏情况下为： O(n2)
例
20
1 215 35 254来自10312
1，3，2，4，1的开销为85并不是最优解。 1，2，4，3，1的开销为72

d(1, {2, 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})} 这一阶段的决策又依赖于下面的计算结果：
lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14
于是，得到了目标函数的界[14, 16]。 需要强调的是，这个解并不是一个合法的选择（可能没有 构成哈密顿回路），它仅仅给出了一个参考下界。
d(1, {2, 3})=min{c12+d(2, {3}), c13+ d(3, {2})}=min{2+5, 3+11}=7(1→2) d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}=min{4+6, 2+12}=10(2→1) d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}=min{7+8, 5+9}=14(3→2) 最后有：
③ 边(u, v) 加入解集合S后，S中不产生分枝；
∞3 3 2 6
C= 3 ∞ 7 3 2 3 7 ∞2 5
2 3 2∞3
6 2 5 3∞
1
52
2
4
3
(a) 5城市的代价矩阵 (b) 城市1→城市4
1
2 5
22
4
3
(c) 城市5→城市2

f5(i, )=min{Cij+f6(1, )}=Ci1, d5(i, 1), i=2, 3, 4, 5 f5(i, )的值列表如下：
1
i 2
f5(i, ) 2
5 3
5 1 2 7
2
2 3 3
3
4 5
7
2 5
6
4 4
5
7

对于k=4, 有

f4(i, S4)=min{Cij+f5(j, S5)}, jS4, f4(i, S4。并且有 xn=(i, ), i=2, 3, …, n,
xn+1=(1, )
4
动态规划模型构造




决策变量：dk=(i, j), 其中i为当前所在的城市, j为下一站将要到达的城市。 状态转移方程：若当前的状态为 xk=(i, Sk) 采取的决策为 dk=(i, j) 则下一步到达的状态为 xk+1=T(xk, dk)=(j , Sk\{j})
9
(i, S3) (2, {3, 4}) (2, {3, 5})
J {3} {4} {3} {5}
Cij 3 5 3 1
S4 {4} {3} {5} {3}
Cij+f4(j, S4) 3+f4(3, {4})=3+6=9* 5+f4(4, {3})=5+11=16 3+f4(3, {5})=3+11=14* 1+f4(5, {3})=1+13=14*
(1, S1) (1, {2, 3, 4, 5})
J {2} {3} {4} {5}
Cij 2 7 2 5
S2 {3, 4, 5} {2, 4, 5} {2, 3, 5} {2, 3, 4}

代 ， 并逐步 衰减ｔ 值， 算 法 终 止 时 的 当 前 解 即 为 所 得 近 似 最 优 解， 这 是 基 于 蒙 特 卡 罗 迭 代 求 解 法 的 一 种 启 发 式 随 机 搜 索 过 程 。退 火 过 程 由冷 却 进 度 表 （ Ｃ ｏ ｏ ｌ ｉ ｎ ｇ Ｓ ｃ ｈ ｅ ｄ ｕ ｌ ｅ ） 控制 ， 包 括 控 制 参数的初值ｔ 及其衰 减因子△ ｔ 、 每个ｔ 值 时的迭代 次数Ｌ 和 停 止 条件 Ｓ 。 ２ ． １ 模 拟 退 火算 法 的模 型 模 拟退火算法 可以分解 为解空间 、 目标 函 数 和初 始 解 三 部分。 模 拟退火的基本 思想 ： （ １ ） 初始化 ： 初 始 温 度 Ｔ（ 充 分大 ） ， 初始解状态Ｓ （ 是 算 法 迭 代 的起 点 ） ， 每个Ｔ 值的迭代次数Ｌ ； （ ２ ） 对ｋ ＝ ｌ ， …… ， Ｌ 做第 （ ３ ） 至第６ 步； （ ３ ） 产生新解Ｓ ； （ ４ ） 计 算 增 量 Ａ ｔ ＝ Ｃ（ Ｓ ） 一 Ｃ （ Ｓ ） ， 其中Ｃ （ Ｓ ） 为评 价函数 ； （ ５ ） 若Ａ ｔ ＜ Ｏ 则 接 受Ｓ
市 出发 ． 不重 复地 遍 历 所 有 城 市 并 回到 起 点 ， 求 一 条 路 程 最 短 的路 径 。 这 个 问题 已被 证 明是 一 个 ＮＰ — Ｃ（ Ｎｏ ｎ ｄ ｅ ｔ ｅ ｍｉ ｒ ｎ ｉ ｓ ｔ ｉ ｃ Ｐ ｏ ｌ ｙ ｎ ｏ — ｍ ｉ ａ ｌ — Ｃ ｏ ｍ ｐ ｌ ｅ ｔ ｅ ｎ ｅ ｓ ｓ ） 问题 ， 其计算复杂度为０ （ ｎ ！） ， 目前 还 不 能 找 出一 个 多 项 式 算 法 解 决 此 类 问题 。但 解 决 此类 问 题 有 较 大 的现 实 意 义 。例 如 ： 在 网络 通信 中求 解 路 由问 题 时 。 可 用 节 点 间 的路 径 长 度 代 表 网 络 节 点 间 的通 信 代 价 ．而求 解 一 条 代 价 最 小 路 由 回路 即 可 转 化 为ｒ Ｉ ＇ Ｓ Ｐ 问 题 的 求 解 下 面将 简述Ｔ Ｓ Ｐ 问 题 的两 种 不 同近 似 算 法 ： 模 拟 退 火算 法 、 遗传算法 。 ２ ． 模 拟 退 火算 法 Ｋ Ｉ Ｒ Ｋ Ｐ Ａ Ｔ Ｒ Ｉ Ｃ Ｋ等 于 １ ９ ８ ３ 年 首 先 提 出模 拟 退 火 算 法 。模 拟 退 火 算 法 来 源 于 固体 退 火 原 理 ， 将固体加温至充分高 ． 再 让 其 徐徐冷 却 ， 加 温时 ， 固体 内 部 粒 子 随 温 升 变 为 无 序 状 ， 内 能 增 大， 而徐徐冷却 时粒子渐趋有序 ， 在每个温 度都达到平 衡态 ， 最 后 在 常 温 时 达 到基 态 ， 内 能 减 为 最 小 。 根 据 Ｍｅ ｔ ｒ ｏ ｐ ｏ ｌ ｉ ｓ 准则 ，

显然 0 0 1， 0 越小， 说明分组的均衡性越 好. 取定一个 后， 0 与 满足条件 3）的分组是 一个均衡分组. 条件 4）表示总巡视路线最短. 此问题包含两方面：a)对顶点分组, b)在每组中 求(单个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存 故多 也不 存在多项式时间内的精确算法.
O—2—5—6—7—E—8—E—11—G—12—H—12 —F—10—F—9—E—7—6—5—2—O O—R—29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17—K—22—23—N—26—P—O O—M—25—20—21—K—18—I—15—14—13—J —19—L—6—M—O O—R—A—33—31—32—35—34—B—1—C—3 — D—4—D—3—2—O
定义 若对于某一对i和j，有 w(vi v j ) w(vi 1v j 1) w(vi vi 1) w(v j v j 1) 则圈Cij将是圈C的一个改进. 二边逐次修正法: 在接连进行一系列修改之后,最后得一个圈,不能 再用此方法改进了，这个最后的圈可能不是最优的, 但是它是比较好的，为了得到更高的精度，这个
现在尝试将顶点分为4组.分组的原则：除遵从 前面准则1、2、3外，还应遵从以下准则： 准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组，同时计算 各组的停留时间,然后用算法一算出各组的近似最 最佳旅行售货员巡回，得出路线长度及行走时间, 从而得出完成巡视的近似最佳时间. 用算法一计 计算时，初始圈的输入与分三组时同样处理.
表3 组名 I II III IV 路 线
（路程单位：公里；时间单位：小时） 路 线 停留 时间 17 16 18 18 行走 时间 5.59 5.69 4.54 4.74 完成巡视 的总时间 22.59 21.69 22.54 22.74 总长度 195.8 199.2 159.1 166

【算法复习二】货郎担（旅行售货商）动态规划一，问题由来货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。

二，问题描述1）货郎担问题提法：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？2）旅行商问题的提法：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

三，问题求解1）动态规划解例题：设v1，v2，……..，vn是已知的n个城镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回v1的最短路程。

分析：设S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。

建模：状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。

最优指标函数fk（i，S）为从v1出发，经过S集合中所有点一次最后到达vi。

决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合到vi 城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为：fk（i，S）= min{ fk-1（j，S、{ j }+dji} j属于Sf0（i，空集）=d1i （k=1，2，…,n-1,i=2,3,…n)求解：K=0f0(2,空集)=d12=6f0(3,空集)=d13=7f0(4,空集)=d14=9当k=1时:从城市V1出发,经过1个城镇到达Vi的最短距离为:f1(2,{ 3 }) = f0 (3,空)+d 32 =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当k=2时,从城市V1出发,中间经过2个城镇到达Vi的最短距离.f2(2,{ 3,4 }) = min[ f1(3,{4})+d32, f1(4,{3})+ d42] =min[14+8,15+5]=20P2(2,{3,4})=4f2(3,{ 2,4 })= min[14+9,13+5]=18P2(3,{2,4})=4f2(4,{ 2,3})= min[15+7,15+8]=22P2(4,{2,3})=2当k=3时:从城市V1出发,中间经过3个城镇最终回到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]=23P3(1,{2,3,4})=3逆推回去,货郎的最短路线是1 2 4 3 1,最短距离为23.四，源码[html] view plaincopyprint?1.#include<iostream>2.#include<iomanip>ing namespace std;4.5.int n;6.int cost[20][20]={};7.bool done[20]={1};8.int start = 0; //从城市0开始9.10.int imin(int num, int cur)11.{12.if(num==1) //递归调用的出口13.return cost[cur][start]; //所有节点的最后一个节点，最后返回最后一个节点到起点的路径14.15.int mincost = 10000;16.for(int i=0; i<n; i++)17.{18.cout<<i<<" i:"<<done[i]<<endl;19.if(!done[i] && i!=start) //该结点没加入且非起始点20.{21.if(mincost <= cost[cur][i]+cost[i][start])22.{23.continue; //其作用为结束本次循环。

组合优化中的旅行推销员问题旅行推销员问题（Traveling Salesman Problem，TSP）是组合优化领域中最经典的问题之一。

该问题的基本描述是：给定一组城市和城市之间的距离，寻找一条最短的路径，使得经过每个城市一次且最终回到起始城市。

TSP在实际生活中有着广泛的应用，例如物流配送、电路板设计和基因序列分析等。

1. 问题描述在旅行推销员问题中，我们考虑有n个城市，城市之间的距离由一个n×n的矩阵D表示。

矩阵D中的元素D[i][j]表示城市i到城市j的距离。

该问题的目标是找到一条从某个城市出发，经过每个城市一次且最终回到出发城市的最短路径。

2. 算法解决方案在组合优化中，各种算法被提出来解决旅行推销员问题。

以下介绍两种常见的解决方案。

2.1 蛮力搜索算法蛮力搜索算法是一种穷举所有可能路径的方法。

其基本思想是通过尝试所有可能的路径组合，计算每条路径的总长度，最后找到最短路径。

蛮力搜索算法的缺点是时间复杂度较高，随着城市数量增加，搜索空间呈指数级增长。

2.2 近似算法近似算法是为了在较短的时间内找到接近于最优解的解决方案。

其中最著名的算法是最近邻算法。

该算法从一个起始城市出发，每次选择距离当前城市最近的未访问城市作为下一个访问城市，直到所有城市都被访问过，并返回起始城市。

虽然最近邻算法不能保证找到最优解，但其时间复杂度低，适用于大规模问题。

3. 实例分析为了更好地理解旅行推销员问题的解决方法，以一个具体的实例进行分析。

假设有5个城市，城市之间的距离矩阵D如下：城市A 城市B 城市C 城市D 城市E城市A 0 1 2 3 4城市B 1 0 5 6 7城市C 2 5 0 8 9城市D 3 6 8 0 10城市E 4 7 9 10 0使用蛮力搜索算法，我们需要计算出所有可能的路径，并计算每条路径的长度，最终找到最短路径。

在本例中，共有5个城市，所以共有5个阶乘（5！= 120）条可能的路径。

基于动态规划算法的旅行商问题求解旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题。

它的任务是在给定一系列城市和每对城市之间的距离（或者称为成本），找到一条经过每个城市一次且回到起始城市的最短路径。

动态规划算法是求解旅行商问题的一种常用方法。

它基于以下思想：将大问题分解为若干个小问题，通过解决小问题的最优解来逐步得到大问题的最优解。

首先，我们需要定义旅行商问题的状态。

在本问题中，我们可以将状态定义为一个二元组 (i, S)，它表示旅行商当前所在的城市为 i，已经遍历过的城市集合为 S。

这里的状态空间是城市集合 C 的幂集除去空集：状态空间：C = {1, 2, ..., n}，其中 n 是城市的数量。

接下来，我们需要定义状态转移方程。

假设当前状态为 (i, S)，我们需要求解的是到达状态 (i, C) 的最短路径。

状态转移方程可以表示为：dp[i][S] = min{dist[i][j] + dp[j][S\{j}]}，其中 j∈S，j≠i其中，dp[i][S] 是从城市 i 出发，经过集合 S 中的城市，最后回到起始城市的最短路径长度。

dist[i][j] 表示城市 i 到城市 j 的距离。

S\{j} 表示从集合 S 中去掉元素 j 后的集合。

最后，我们需要定义问题的边界条件。

当集合 S 中只有一个城市 i 时，经过城市 i 后回到起始城市的路径长度就是从起始城市到达城市 i 的距离。

所以边界条件可以表示为：当 |S| = 1 时，dp[i][S] = dist[i][1]接下来，我们使用动态规划算法来解决旅行商问题。

1. 创建一个二维数组 dp[n][2^n]，其中 n 是城市的数量。

初始化数组 dp 的所有元素为无穷大。

2. 对于每个城市 i，将 dp[i][∅]（空集）的值设为 dist[i][1]。

3. 对于集合 S 的大小从 2 到 n-1 的每个值，依次遍历每个城市 i。

旅⾏售货员问题（分⽀限界法）⼀、实验内容运⽤分⽀限界法解决0-1背包问题（或者旅⾏售货员问题、或者装载问题、或者批处理作业调度）使⽤优先队列式分⽀限界法来求解旅⾏售货员问题⼆、所⽤算法基本思想及复杂度分析1.算法基本思想分⽀限界法常以⼴度优先或以最⼩耗费有限的⽅式搜索问题的解空间树。

问题的解空间树是表⽰问题解空间的⼀棵有序树，常见的有⼦集树和排列树。

在搜索问题的解空间树时，分⽀限界法和回溯法的主要区别在于它们对当前扩展节点所采⽤的扩展⽅式不同。

在分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展节点。

活结点⼀旦成为扩展节点，就⼀次性产⽣其所有⼉⼦节点。

在这些⼉⼦节点中，导致不可⾏解或导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活结点表中。

此后，从活结点表中取下⼀节点为当前扩展节点。

并重复上述节点扩展过程。

这个过程移⾄持续到找到所需的解或活结点表为空为⽌。

从活结点表中选择下⼀扩展节点的不同⽅式导致不同的分⽀限界法。

最常见的有以下两种⽅式：（1）队列式分⽀限界法队列式分⽀限界法将活结点表组织成⼀个队列，并按队列的先进先出原则选取下⼀个节点为当前扩展节点。

（2）优先队列式分⽀限界法优先队列式的分⽀限界法将活结点表组织成⼀个优先队列，并按优先队列中规定的节点优先级选取优先级最⾼的下⼀个节点成为当前扩展节点。

2.问题分析及算法设计问题分析：（1）解旅⾏售货员问题的优先队列式分⽀限界法⽤优先队列存储活结点表。

（2）活结点m在优先队列中的优先级定义为：活结点m对应的⼦树费⽤下界lcost。

（3）lcost=cc+rcost，其中，cc为当前结点费⽤，rcost为当前顶点最⼩出边费⽤加上剩余所有顶点的最⼩出边费⽤和。

（4）优先队列中优先级最⼤的活结点成为下⼀个扩展结点。

（5）排列树中叶结点所相应的载重量与其优先级（下界值）相同，即：叶结点所相应的回路的费⽤(bestc)等于⼦树费⽤下界lcost的值。

算法设计：（1）要找最⼩费⽤旅⾏售货员回路，选⽤最⼩堆表⽰活结点优先队列。

旅行售货员问题传统的旅行售货员问题可以概述如下：设有n个城市，以V1 ，V2 ，…V n表示之，用d ij表示城市V i到城市V j之间的距离，一个推销员从某城市(不妨假设从城市V1)出发到其他城市去一次而且仅一次，然后回到原来的城市(城市V1)，问其应该选择什么样的行走路线才能使得总的旅行路程最短。

把这个问题抽象成图论问题就是给定一个连通无向图G(V,E)，其中V＝{V1 ,V2,…V n}是顶点(城市)的集合，E是顶点间边的集合，表示相应城市间的旅行路线，即E={e=(V i,V j)；顶点V i与V j间有边e},每个边e∈E上有非负权重w(e)=w(V i,V j)=d ij，表示顶点V i即城市V i到顶点V i(即城市V j)的距离，问题就是要确定图G的一个圈，它过每个顶点一次且仅一次，而且使得该圈的总权(即圈上所有边的权之和)最小。

这个圈在图论里称为Hamilton圈，简称H圈。

由于G(V,E)的边是无向的，相邻的边和顶点可以通过边进入顶点，也可以通过顶点进入边。

这样，寻找售货员最优旅行路线的问题就可以归结为如下的图论问题：给定连通图G(V,E)，对每条边e= (V i,V j)∈E对应的顶点V i与V j间添加反向边e'=(V j,V i)，得到双倍于G的另外一个连通图G'=(V,E')，求E1⊆E'使得G1(V,E1)为H圈且总权为∑w(e)最∈E1e小。

为叙述方便，若e= (V i ,V j )，则记为e i ,j ∈E,而相应的添加边为e j ,i 。

与边e i ,j ∈E '相对应，设定一个0-1整数变量x i ,j 。

若e i ,j ∈E '，即称边是从V i 到V j 的，或称为弧。

这样，我们就可以把无向图理解为有向图D (V,E)。

每一个E 1⊆E '唯一对应一组x i ,j 的值，反之亦然。

我们称x i ,j 为E 1的值系。

旅行售货员问题描述：由n个顶点构成的图，要求走遍所有的点且每个顶点只能走一次，最后回到出发点，使所走过的路径和最小，求最小值。

算法描述：通常以广度优先或以最小耗费优先的方式搜索问题的解空间树，只需求出一个解或是在满足约束条件的解中找出在某种意义下的最优解即结束遍历，在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，不可行解或非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

算法设计：1.构造出解空间树（仅使用一个优先队列来存储活节点，其中每个活节点都储存从根到该活结点的相应路径）2.利用二维数组保存图信息City_Graph[MAX_SIZE][MAX_SIZE]，其中City_Graph[i][j]的值代表的是城市i与城市j之间的路径费用，一旦一个城市没有通向另外城市的路，则不可能有回路，不用再找下去了3. 我们任意选择一个城市，作为出发点。

（因为最后都是一个回路，无所谓从哪出发）举例：某售货员要到若干个城市推销商品，已知各城市之间的路程（或旅费）。

他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线（或总的旅费最小）。

程序：#include "stdafx.h"#include <stdio.h>#include <istream>using namespace std;//---------------------宏定义------------------------------------------#define MAX_CITY_NUMBER 10 //城市最大数目#define MAX_COST 10000000 //两个城市之间费用的最大值//---------------------全局变量----------------------------------------int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组int City_Size; //表示实际输入的城市数目int Best_Cost; //最小费用int Best_Cost_Path[MAX_CITY_NUMBER];//最小费用时的路径//------------------------定义结点--------------------------------------- typedef struct Node{int lcost; //优先级int cc; //当前费用int rcost; //剩余所有结点的最小出边费用的和int s; //当前结点的深度，也就是它在解数组中的索引位置int x[MAX_CITY_NUMBER]; //当前结点对应的路径struct Node* pNext; //指向下一个结点}Node;//---------------------定义堆和相关对操作-------------------------------- typedef struct MiniHeap{Node* pHead; //堆的头}MiniHeap;//初始化void InitMiniHeap(MiniHeap* pMiniHeap){pMiniHeap->pHead = new Node;pMiniHeap->pHead->pNext = NULL;}//入堆void put(MiniHeap* pMiniHeap, Node node){Node* next;Node* pre;Node* pinnode = new Node; //将传进来的结点信息copy一份保存//这样在函数外部对node的修改就不会影响到堆了pinnode->cc = ;pinnode->lcost = node.lcost;pinnode->pNext = node.pNext;pinnode->rcost = node.rcost;pinnode->s = node.s;pinnode->pNext = NULL;for (int k = 0; k<City_Size; k++){pinnode->x[k] = node.x[k];}pre = pMiniHeap->pHead;next = pMiniHeap->pHead->pNext;if (next == NULL){pMiniHeap->pHead->pNext = pinnode;}else{while (next != NULL){if ((next->lcost) >(pinnode->lcost)){ //发现一个优先级大的，则置于其前面pinnode->pNext = pre->pNext;pre->pNext = pinnode;break; //跳出}pre = next;next = next->pNext;}pre->pNext = pinnode; //放在末尾}}//出堆Node* RemoveMiniHeap(MiniHeap* pMiniHeap){Node* pnode = NULL;if (pMiniHeap->pHead->pNext != NULL){pnode = pMiniHeap->pHead->pNext;pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext;}return pnode;}//---------------------分支限界法找最优解--------------------------------void Traveler(){int i, j;int temp_x[MAX_CITY_NUMBER];Node* pNode = NULL;int miniSum; //所有结点最小出边的费用和int miniOut[MAX_CITY_NUMBER];//保存每个结点的最小出边的索引MiniHeap* heap = new MiniHeap; //分配堆InitMiniHeap(heap); //初始化堆miniSum = 0;for (i = 0; i<City_Size; i++){miniOut[i] = MAX_COST; //初始化时每一个结点都不可达for (j = 0; j<City_Size; j++){if (City_Graph[i][j]>0 && City_Graph[i][j]<miniOut[i]){//从i到j可达，且更小miniOut[i] = City_Graph[i][j];}}if (miniOut[i] == MAX_COST){// i 城市没有出边Best_Cost = -1;return;}miniSum += miniOut[i];}for (i = 0; i<City_Size; i++){ //初始化的最优路径就是把所有结点依次走一遍Best_Cost_Path[i] = i;}Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数pNode = new Node; //初始化第一个结点并入堆pNode->lcost = 0; //当前结点的优先权为0 也就是最优pNode->cc = 0; //当前费用为0（还没有开始旅行）pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始化的miniSumpNode->s = 0; //层次为0pNode->pNext = NULL;for (int k = 0; k<City_Size; k++){pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就是初始化的路径}put(heap, *pNode); //入堆while (pNode != NULL && (pNode->s) < City_Size - 1){//堆不空不是叶子for (int k = 0; k<City_Size; k++){Best_Cost_Path[k] = pNode->x[k]; //将最优路径置换为当前结点本身所保存的}/** * pNode 结点保存的路径中的含有这条路径上所有结点的索引* * x路径中保存的这一层结点的编号就是x[City_Size-2]* * 下一层结点的编号就是x[City_Size-1]*/if ((pNode->s) == City_Size - 2){ //是叶子的父亲int edge1 = City_Graph[(pNode->x)[City_Size - 2]][(pNode->x)[City_Size - 1]];int edge2 = City_Graph[(pNode->x)[City_Size - 1]][(pNode->x)[0]];if (edge1 >= 0 && edge2 >= 0 && (pNode->cc + edge1 + edge2) < Best_Cost){ //edge1 -1 表示不可达//叶子可达起点费用更低Best_Cost = pNode->cc + edge1 + edge2;pNode->cc = Best_Cost;pNode->lcost = Best_Cost; //优先权为 Best_CostpNode->s++; //到达叶子层}}else{//内部结点for (i = pNode->s; i<City_Size; i++){ //从当前层到叶子层if (City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){ //可达//pNode的层数就是它在最优路径中的位置int temp_cc = pNode->cc + City_Graph[pNode->x[pNode->s]][pNode->x[i]];int temp_rcost = pNode->rcost - miniOut[pNode->x[pNode->s]];//下一个结点的剩余最小出边费用和//等于当前结点的rcost减去当前这个结点的最小出边费用if (temp_cc + temp_rcost<Best_Cost){ //下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解for (j = 0; j<City_Size; j++){ //完全copy路径，以便下面修改temp_x[j] = Best_Cost_Path[j];}temp_x[pNode->x[pNode->s + 1]] = Best_Cost_Path[i];//将当前结点的编号放入路径的深度为s+1的地方temp_x[i] = Best_Cost_Path[pNode->s + 1]; //??????????????//将原路//径中的深度为s+1的结点编号放入当前路径的//相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换Node* pNextNode = new Node;pNextNode->cc = temp_cc;pNextNode->lcost = temp_cc + temp_rcost;pNextNode->rcost = temp_rcost;pNextNode->s = pNode->s + 1;pNextNode->pNext = NULL;for (int k = 0; k<City_Size; k++){pNextNode->x[k] = temp_x[k];}put(heap, *pNextNode);delete pNextNode;}}}}pNode = RemoveMiniHeap(heap);}}int main(){int i, j;scanf_s("%d", &City_Size);for (i = 0; i<City_Size; i++){for (j = 0; j<City_Size; j++){scanf_s("%d", &City_Graph[i][j]);}}Traveler();printf("%d /n", Best_Cost);system("pause");return 1;}。

可以证明，即使费用函数具有三角不等式性质,旅行售货员问题仍为 NP完全问题。所以设计一个近似算法。当费用函数满足三角不等式时， 该算法不会超过最优旅行售货员回路费用的2倍。
在费用函数不一定满足三角不等式的一般情况下， 不存在具有常数性能比的解TSP问题的多项式时间近似算法, 除非P=NP。换句话说，若P≠NP，则对任意常数ρ>1，不存在性能比为ρ 的解旅行售货员问题的多项式时间近似算法。
回溯法以这种工作方式递归地在解空间中搜索，直至找到所 要求的解或解空间中已无活结点时为止。
二.常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。
为了避免生成那些不可能产生最佳解的问题状态，要不断 地利用限界函数(bounding function)来处死(剪枝)那些 实际上不可能产生所需解的活结点，以减少问题的计算量。 具有限界函数的深度优先生成法称为回溯法。 回溯法 = 穷举 + 剪枝
6D
6D
14 J C 30
C 30 24 K
E被扩展后，它的儿子结点J,K被依次插入当前堆中
14 J
14 J
24 K
C 30 24 K C 30
11 H 14 J C 30
11 H I 26 24 K
D被扩展后，它的儿子结点H,I被依次插入当前堆中
I 26
{}； B{E,D,C}； E{D, J,K, C}； D{H,J,K,I,C}； H{J,K,I,C}；J{K,I,C}； K{I,C}；I{C}；C{}.
2. 当i<n时，当前扩展节点位于排列树的第i-1层。
①图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径， 且当x[1:i]的费用小于当前最优值时算法进入树的第i层， ②否则将剪去相应的子树。

05 实际应用与案例分析
在路线规划中的应用
总结词
旅行推销员问题在路线规划中具有广泛的应用，通过优 化路径选择，降低成本和提高效率。
详细描述
在路线规划中，旅行推销员问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，旨在寻找 一条最短路径，使得一个旅行推销员能够访问一系列城 市并返回出发城市，同时最小化总旅行距离。通过应用 计算机算法和优化技术，可以解决路线规划中的各种问 题，如物流配送、公共交通和出租车服务等。
02 旅行推销员问题的传统解法
暴力法
总结词
通过穷举所有可能的路径组合来寻找最优解。
详细描述
暴力法是一种简单直接的方法，通过尝试所有可能的路径组合来找出最短路径。对于旅行推销员问题，暴力法会 尝试所有可能的路径组合，然后选择最短的一条。然而，由于组合数量随着城市数量的增加呈指数级增长，暴力 法在处理大规模问题时效率极低，需要消耗大量的时间和计算资源。
针对传统智能优化算法的不足，进行改进和优化，提高算 法的搜索效率和精度。例如，改进遗传算法、模拟退火算 法等。
并行计算与分布式计算
并行计算框架
利用并行计算框架，如Hadoop、Spark等，将问题分解为多个子 任务，并行处理子任务，提高计算效率。
分布式计算模型
采用分布式计算模型，将问题分解为多个子问题，分布到多个节点 上进行处理，实现大规模数据的快速处理。
数学优化方法
总结词
利用数学建模和优化理论来求解最短路径问题。
详细描述
数学优化方法是一种基于数学建模和优化理论的方法，通过建立旅行推销员问题的数学模型，利用优 化算法来求解最短路径。这种方法在理论上可以处理大规模问题，但在实际应用中，由于计算复杂度 较高，对于大规模问题求解效率较低。

动态规划算法的应用课程名称：****************院系：**************************学生姓名：******学号：************专业班级：***************************** 指导教师：******2013年12月27日动态规划的应用摘要：旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。

该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。

动态规划（ dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。

利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。

本次课程设计运用动态规划解决旅行售货员问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。

前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。

依次解决各子问题，最后一个子问题就是初始问题的解。

通过图的关系矩阵来表示个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。

关键字:旅行商问题动态规划法图矩阵目录第一章绪论 (1)1.算法介绍 (1)2.算法应用 (1)第二章动态规划理论知识 (2)2.1动态规划的基本思想 (2)2.2动态规划设计步骤 (2)第三章旅行售货员问题 (3)3.1问题描述：旅行售货员问题 (3)3.2算法设计内容 (3)3.3算法分析 (3)3.4流程图 (4)第四章物流配送网络 (5)第五章结论 (7)参考文献 (8)附件 (9)第一章绪论1.算法介绍动态规划（ dynamic programming ）是解决多阶段决策过程最优化问题的一种数学方法。

24
（2）下界b3 为便于描述下界b3，先定义如下符号： T：对称TSP问题； n：结点总个数； w(i,j)：结点i与j之间距离； dmin(i, k)：与第i个结点关联的所有边中第k (k = 1, 2, 3)
长边的长度；
dmin_j(i, k)：与第i个结点关联的所有边中第k (k = 1, 2, 3) 长边的另一个结点的编号(其中一个结点编号为i)；
15
考虑个顶点的完全图Kn ，则解TSP就相
当于在中求一条总长度最短的Hamilton回路。现在，
对每条边ej，定义一个变量xj与之对应，这样，TSP 的一条路线T，即Kn的一条Hamilton回路，就可对应 一个向量X={x1,x2,….xm}，其中，
x j 1, x j 0,
需要到城市2、3、…、n去推销货物，最后返回城
市1，若任意两个城市间的距离已知，则该旅行商 应如何选择其最佳行走路线？
3
TSP在图论意义下又常常被称为最小Hamilton圈问 题，Euler等人最早研究了该问题的雏形，后来由英国的 Hamilton爵士作为一个悬赏问题而提出。但这个能让普通人 在几分钟内就可理解的游戏之作，却延续至今仍未能完全解 决，成了一个世界难题。
iS jS
xij 0, 1
i V j V S V , 2 S n 1
(7 1) (7 2) (7 3)
模型中，为集合中所含图的顶点数。约束
（7－1）和（7－2）意味着对每个点而言，仅有一条边
进和一条边出；约束（7－3）则保证了没有任何子回路
解的产生。于是，满足约束（7－1）、（7－2）和（7
第7章
旅行商问题
1
第7章
目录 旅行商问题

旅⾏售货员问题旅⾏售货员问题【题⽬】某售货员要到4个城市去推销商品，已知各城市之间的路程，如右图所⽰。

请问他应该如何选定⼀条从城市1出发，经过每个城市⼀遍，最后回到城市1的路线，使得总的周游路程最⼩？并分析所设计算法的计算时间复杂度。

【分析】该题利⽤回溯法求解，此时需要确定解空间的类型：我们可以知道该解空间为⼀棵排列树。

我们假设初始的⼀条路线为x，x中的值为 1，2，3，……，n，表⽰该路线为由城市1依次经过城市2、3……到n后再回到城市1（当然是假设该路线存在）。

如果不存在的话，我们只需改变⼀下这个排列的排列⽅式，再进⾏判断，所以可想⽽知，我们可以知道该解空间是⼀棵排列树。

当然上述的说法，只是单纯的穷举，这并不是我们想要的回溯法，我们通过递归实现，在递归的过程中适当地“剪枝”即除去那些不可能形成最优解的解。

现在我们来确定⼀下可⾏的约束条件，当我们进⾏递归搜索，搜索到第t层时，我们需要判断⼀下x[t]所代表的城市是否与上⼀层x[t-1]所代表的城市有“路”，如果没有的话，需要改变x[t]的值，然后继续上述判断，当出现⼀个满⾜条件的x[t]后还要判断当前从1到t-1所⾛的路程cc加上x[t]与x[t-1]的距离是否⼩于当前已经记录的最优解（最优解的初始值是⼀个⾜够⼤的数），如果到t的距离⽐当前最优解还要⼤的话，那么再以这条路线搜索下去的话回到城市1的路程⼀定⽐当前最优解还⼤，所以我们没有必要对这条路线进⾏下⼀步的搜索。

最后我们来确定当搜索到叶⼦结点的时候我们该如何处理？已知搜索到t层时，若t = n，说明已经搜索到了叶⼦结点，这个时候我们还需做上述所说的两个判断，如果两个判断都通过的话，说明该解⽐当前最优解还优，那么我们需要将该解记录下来，并记录该解的最优值。

【伪代码】void travel(int t) {if(t到达第n层即搜索到叶⼦结点) {if(城市x[t-1]可以到达城市x[t]，并且城市x[t]可以回到城市1，且此时所⾛的路程cc加上x[t-1]与x[t]的距离和x[t]与1的距离⼩于当前最优值bestc) {将最优解记录下来;将最优值记录下来;}return;}for(int i = t; i < n; i++) {if(城市x[t-1]能达到城市x[i]即这两个城市间有边，并当前所⾛的路程cc加上这两个城市的距离没有⽐当前最优值bestc⼤) {swap(x[i], x[t]);修改此时所⾛的路程cc;进⼊下⼀层递归;恢复原来cc的值;swap(x[i], x[t]);}}}【程序】⽤C++语⾔编写程序，代码如下：#include<iostream>using namespace std;const int INF = 10000000;int n, cc = 0, bestc = INF;int **g;int *x, *bestx;void travel(int t) {if (t == n) {if (g[x[t - 1]][x[t]] != INF && g[x[t]][1] != INF &&(cc + g[x[t - 1]][x[t]] + g[x[t]][1] < bestc || bestc == INF)) { for (int i = 0; i < n + 1; i++)bestx[i] = x[i];bestc = cc + g[x[t - 1]][x[t]] + g[x[t]][1];}return;}for (int i = t; i < n; i++) {if (g[x[t - 1]][x[i]] != INF && (cc + g[x[t - 1]][x[i]] < bestc|| bestc == INF)) {swap(x[i], x[t]);cc += g[x[t - 1]][x[t]];travel(t + 1);cc -= g[x[t - 1]][x[t]];swap(x[i], x[t]);}}}void output() {cout << bestc << endl;cout << bestx[1];for (int i = 2; i < n + 1; i++)cout << " " << bestx[i];cout << " " << bestx[1] << endl;}int main() {n = 4;g = new int*[n + 1];x = new int[n + 1];bestx = new int[n + 1];for (int i = 0; i < n + 1; i++) {g[i] = new int[n + 1];x[i] = i;for (int j = 0; j < n + 1; j++)g[i][j] = INF;}}g[1][2] = g[2][1] = 30;g[1][3] = g[3][1] = 6;g[1][4] = g[4][1] = 4;g[2][3] = g[3][2] = 5;g[2][4] = g[4][2] = 10;g[3][4] = g[4][3] = 20;travel(2);output();return 0;}【结果】先设置好城市间的距离，调⽤回溯⽅法，输出最优值（最⼩路程）和最优解（路线）：该算法的时间复杂度为O(n!)。

TSP问题的动态规划解法第十七组：3103038028 郑少斌3103038029 王瑞锋3103038035 江飞鸿3103038043 韩鑫3103055004 唐万强1．TSP问题简介旅行商问题（Traveling Salesman Problem,简称TSP, 亦称为货单郎问题）可以描述为：对于N 个城市，它们之间的距离已知，有一旅行商要从某一城市走遍所有的城市，且每一城市只能经过一次，最后回到出发的城市，问如何选择路线可使他走过的路径最短。

这是一个典型的组合优化问题。

它有很强的现实意义，可以应用于交通运输，物资调配，旅游线路设置。

对于了解某个国家地理分布也有一定的现实意义。

这个问题的解法有很多种，在这里我们尝试使用最优控制中的动态规划的相关知识来进行求解。

2．TSP问题分析对于这个问题，我们首先想到的是应用穷举法进行解答，但是这个方法时间和空间的复杂度很高。

从表面上看，TSP 问题很简单，其实则不然。

对于N 个城市的TSP,存在的可能路径为（N-1）!/2条，当N较大时，其数量是惊人的。

计算每条路经都需求出N 个距离之和，这样各种路径及其距离之和的计算量正比与N!/2.用搜索法要求就规模大的TSP是不现实的。

例如使用1GFLOPs 次的计算机搜索TSP 所需的时间如下表所示 城市数7152050100200加法量 3105.2⨯ 11105.6⨯ 18102.1⨯ 64105.1⨯ 157105⨯ 37410搜索时间s 5105.2-⨯1.8h350yy 48105⨯ y 14210y 35810由上可知，对于这个问题采用穷举法进行解答是不现实的，这就要求我们采用其他的方法进行解答。

3． 其他求解TSP 问题的方法*贪心法a. 所谓贪心法，就是在组合算法中，将每一步都取局部最优的求解方法。

b. 下表表示用贪心法求解TSP 的过程。

先将各城市间的距离用行列式形式表示，主对角线上用∞表示。