课程设计论文-动态规划：货郎担问题算法设计与实现

《课程设计论文-动态规划：货郎担问题算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计（论文）课程名称：系统优算法设计与实现题目：动态规划：货郎担问题算法设计与实现院（系）：管理学院专业班级：信管1501姓名：学号：指导教师：2017年7月18日西安建筑科技大学课程设计（论文）任务书专业班级：信管1501学生姓名：指导教师（签名）：一、课程设计（论文）题目动态规划：货郎担问题算法设计与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现

2、的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：货郎担问题（也称TSP问题），其一般提法为：有n个城市，用1，2，…，n表示，城i,j之间的距离为cij，有一个货郎从城市1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短。S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。其动态规划递推关系为　f(i,S)=mi

3、n{cij+g(j,S-{j})}　f(1,V-{1})=min{c1k+g(k,V-{1,k})}  (2≤k≤n)要求：1．提交正确的和完整的程序设计代码。2．提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.《运筹学》.清华大学出版社，2012五、审核批准意见教研室主任（签字）设计总说明货郎担问题（TSP问题）是指货郎要到n个城市售卖货物然后回到出发城市，要求各个城市经历一次且仅经历一次，并要求所走的路程最短。该问题又称为旅行商问题、邮递员问题、售货员问题，是图问题中

4、最广为人知的问题。动态规划算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。本次课设运用动态规划解决货郎担问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题最后一个子问题就是初始问题的解。通过图的关系矩阵来表示各个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。关键字：货郎担问题动态规划图矩阵目录

5、1绪论11.1内容简介11.2本次课设目的11.3课设内容22（此处用你的题目中的重点研究部分名称代替）设计说明32.1程序设计过程详述32.2编程实现过程详述32.4原代码43实验研究小结73.1使用说明详述73.1.1本部分功能操作注意事项73.1.2本部分功能与其他系统的关系73.2测试案例详述8参考文献10第1页共15页1绪论1.1内容简介货郎担问题(TSP)是指在城镇1~n中，已知各城市距离，货郎从城镇1出发，经过所有城镇一次，且仅一次，最后仍回到原出发的城镇1，应如何选择行路线可使总行程最短1.2本次课设目的设计出算法将待求解问题分解成若干个相互重叠的子

6、问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。从而求出货郎在1～n个城市中以第一个城市为起点走过n个城市并最终回到第一个城市的最短距离和路线。1.3课设内容货郎担问题（也称TSP问题），其一般提法为：有n个城市，用1，2，…，n表示，城i,j之间的距离为cij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短。因此，假设周游路线

7、是开始于结点1并终止于结点1的一条简单路径。每一条周游路线都由一条边〈1,k〉和一条由结点k到结点1的路径所组成,其中k∈V-{1};而这条由结点k到结点1的路径通过V-{1,k}的每个结点各一次。容易看出,如果这条周游路线是最优的,那么这条由k到1的路径必定是通过V-{1,k}中所有结点的由k到1的最短路径,因此最优性原理成立。设第10页共15页(i,S)是由结点i开始,通过S中的所有结点,在结点1终止的一条最短路径长度。f(1,V-{1})是一条最优的周游路线长度。于是,可以得出f(1,V-{1})=min{c1k +g(k,V-{1,k})}  2≤k≤n