设为首页
收藏本站
切换到宽版
用户名
Email
自动登录
找回密码
密码
登录
立即注册
快捷导航
网站首页
大学课后答案
毕业设计
高中课后答案
初中课后答案
小学课后答案
赞助我们
搜索
搜索
热搜:
物理答案
英语答案
高数答案
线性代数
本版
帖子
答案家
»
论坛
›
毕业设计
›
化学|环境|生物|医学|制药
›
2018使用动态规划解决旅行商问题
返回列表
查看:
466
|
回复:
0
2018使用动态规划解决旅行商问题
[复制链接]
9927939
9927939
当前离线
积分
41
1
主题
1
帖子
41
积分
幼儿园
幼儿园, 积分 41, 距离下一级还需 59 积分
幼儿园, 积分 41, 距离下一级还需 59 积分
积分
41
发消息
发表于 2018-8-14 17:34:19
|
显示全部楼层
|
阅读模式
【摘要】旅行商问题是指给定一组城市和道路,求一条从指定城市出发、通过所有其它城市一次、再返回出发城市的代价最小的路径。旅行商问题是一个经典的NP完全问题,其传统的求解算法为穷举法,按所有可能的路径计算一遍,比较所有的计算结果,选择其中的最短路径。
/6/view-10686688.htm
【关键词】动态规划;旅行商;算法
二、动态规划求解策略
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,希望找到具有最优解的那个解。一个动态规划算法通常可按以下几个步骤进行:
(1) 找出最优解的性质,并刻画其结构
(2) 递归定义最优值的求解公式
(3) 以自底向上的方式计算最优值
(4) 根据计算时得到的信息,构造一个最优解
三、旅行商问题的动态规划实现算法
用程序来模仿动态规划算法,最重要的是一个分段过程,它与传统算法的区别是“以自底向上的方式计算出最优值”,我们以这一条准则分段。
在第一次遍历所有的城市流时,每相邻的两个城市流,前三个字符相同的,我们判断一下最后两个字符决定的路径长度,删除路径较长的城市流,保存路径较短的城市流,由于删除了一个城市流,所以我们需要从当前的城市流重新比较一次(反映在一个循环中,就应该是当前的index减1)。当然,在这个比较过程中,我们把计算出的每一个长度都保存起来,这样,我就能避免很多重复计算,这也正是使用动态规划的益处!反映到程序当中,这需要一个包含循环的迭代函数来描述:
private void guihua(int temp) {
if (list.size() == 1) {
this.firnalRoad = list.get(0);
this.min = this.store.get(list.get(0)) + "";
return;
}
for (int i = 0; i = nextValue) {
list.remove(i);
} else {
list.remove(next);
}
i--;
}
}
this.guihua(temp - 1);
}
4.测试实例
(1) first为{{0, 1, 2, 3}, {3, 0, 4, 6}, {4, 2, 0, 8}, {4, 3, 9, 0}};
运行结果为:
路径是:3201
城市顺序:0->3->1->2->0
最小值:14.0
生成所有合法城市流用时:15毫秒
动态规划求解过程用时:0毫秒
(2) first为{{0,2,1,3,4}, {1,0,4,4,2}, {5,4,0,2,2}, {5,2,2,0,3}, {4,2,4,2,0}};
运行结果为:
路径是:20413
城市顺序:0->2->4->3->1->0
最小值:8.0
生成所有合法城市流用时:62毫秒
动态规划求解过程用时:0毫秒
看第2个例子,输出城市顺序是“0->2->4->3->1->0”,由于我们是从0开始计数的,所以与上面数学计算中输出的城市顺序相同,并且最小值为8.0,也是正确的。可以用数学计算方法验证一下,以上例子的输出都是正确的。
四、结束语
动态规划法是一种有着广泛应用的算法,它的优越性在于省略了很多重复计算,所以在数学计算中应用较多。但随着城市数量的增多,动态规划算法求解问题的时间还是保持很大的增长率,所以动态规划虽然提供了一种问题的求解办法,但并不完美。
作者简介
申永康(1997),男,汉族,山东日照,高中生,山东省日照一中。
回复
举报
返回列表
高级模式
B
Color
Image
Link
Quote
Code
Smilies
您需要登录后才可以回帖
登录
|
立即注册
本版积分规则
发表回复
回帖后跳转到最后一页
CopyRight(c)2016 www.daanjia.com All Rights Reserved. 本站部份资源由网友发布上传提供,如果侵犯了您的版权,请来信告知,我们将在5个工作日内处理。
快速回复
返回顶部
返回列表