一,问题由来
货郎担问题也叫旅行商问题,即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属于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
当k=1时:
从城市V1出发,经过1个城镇到达Vi的最短距离为:
f1(2,{ 3 }) = f0 (3,空)+d
32 =7+8=15
f1(2,{ 4 }) = f0 (4,空)+d
42 =9+8=14
f1(3,{ 2 }) = f0 (2,空)+d
23 =6+9=15
f1(3,{ 4 }) = f0 (4,空)+d
43 =9+5=14
f1(4,{ 2 }) = f0 (2,空)+d
24 =6+7=13
f1(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]=20
P2(2,{3,4})=4
f2(3,{
2,4 })= min[14+9,13+5]=18
P2(3,{2,4})=4
f2(4,{ 2,3})= min[15+7,15+8]=22
P2(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]=23
P3(1,{2,3,4})=3
逆推回去,货郎的最短路线是1
2 4 3 1,最短距离为23.
四,源码
源码解析:核心是动态规划,自底向上的思想。
写法是递归写法,自顶向下递归调用。
第一次调用:起点0,第一个节点是1时候
{
进入递归---->value = d01 +imin(3,1)
{
进入递归-----value = d12 +imin(2,2)
{
进入递归---->value = d23 +imin(1,3)
{
进入递归---->return d30;
}
……}
……}
……}
分享到:
相关推荐
货郎担问题是运筹学中的一个著名命题,目前使用分值定界法及动态规划法比较多,本文介绍使用元素判别值进行求解及其算法设计和程序实现。它比现行方法简单有效。
使用动态规划实现货郎担问题,计算出代价矩阵的最优解,即最短路径
这是一份详细的货郎担算法,采用的是蛮力算法求解思想。
c语言编写的货郎担算法,可以运行,大家参考参考
货郎担 分枝限界算法图形求解货郎担问题的分枝限界算法图形演示
这个是一个非常详细的货郎担算法的例子,内部有一个详细的API介绍
货郎担限界算法 c语言
里面是货郎担问题的各种接方法,包括动态规划,穷举搜索, 解决方案: 1.穷举法? 2.最短路标号法? 3.指派问题? 4.整数规划? 5.动态规划?
回溯算法代码 货郎担问题 哈密尔顿回路 代码 flash演示
Delphi 货郎担算法类及演示程序,程序还有些不是很满意,主要是一些细节问题,主算法基本没什么问题的了,大家有兴趣就看看吧。在这个程序内,为城市加了影射圈。
用佳点集实现遗传算法,解决货郎担问题,也就是Tsp问题,整个程序用Java实现,为便于学习,程序添加了详尽的注释,以及Javadoc帮助文档。整个程序只注重算法本身,没有添加任何包括图形界面在内的影响阅读的代码。...
关于旅行商问题 旅行售货员问题 货郎担问题的一些文章,均是pdf格式的,基本都是中国期刊网上下载的,是付费下载的哦!!一般地方是找不到的!
TSP问题(又名:旅行商问题,货郎担问题)遗传算法通用matlab程序
大学C++数据结构与算法课程中的实验,里面有很多个算法设计的实验源代码,绝对可靠,有货郎担、二分检索
采用蚁群算法计算货郎担通过 34 个城市一次回到原点的最短距离 可短时间解决这个 NP 难的 TSP 问题 内含运行文件生成的两张图 注释较详细
货郎担问题的解决,很好用的哦,可以直接运行
matlab 实现货郎担问题的源代码,其使用的而算法是模拟退火算法。
模拟退火算法求解货郎担问题(用C#实现).zip
TSP货郎担应用动态归划法求解 求从某个节点出发, 遍历余下n-1各节点后再回到出发点的最小成本周游路线.
求解货郎担佳点集遗传算法的文档,利用了佳点集算法,更加的优化