毕业论文【设计】动态规划-货郎担问题算法设计与实现

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

1、必姜達統科技A#课程设计（论文）任务书专业班级：信管1501学生姓名：_指导教师（签名）：「二7W趕蚕评••（¥支-）-If••动态规划：货郎担问题算法设计与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重耍组成部分,其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实鉍问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步増强实际工程训练。三、本次课程设计（论文）任务的主要内容和要

2、求设计内容：货郎担问题（也称TSP问题），其一般提法为：有n个城市，用1，2,…，n表示，城i,j之间的距离为有一个货郎从城市1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短。5’表示从W到「7屮间所可能经过的城市集合，S实际上是包含除「7和「7两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。状态变量（/,幻表示：从点出发，经过S集合中所有点一次最后到达r/。其动态规划递推关系为/（/，5）=min{}/（l,=min{^+k,f’-{l,々}）}（2彡杉n）要求：1.提交正确的和完整的程序设计代码

3、。2.捉交设计说明15。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题F1??景的有关资料。主要参考文献：1.胡运权.《运筹学》.淸平人学出版社，2012五、审核批准意见教研室主任（签字）设计总说明货郎枳M题（TSP问题）是指货郎要到n个城市售卖货物然后回到出发城市，要求各个城市经历一次且仅经历一次，并要求所走的路程最短。该问题又称为旅行商问题、邮递员问题、售货员问题，是图问题中最广为人知的M题。动态规划算法是解决多阶段决策过程最优化W题的一种常用方法，难度比较大，技巧性也很强。本次课设运用动态规

4、划解决货郎枳问题，动态规划的基本思想是：把求解的fuj题分成许多若干阶段或许多子fuj题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题吋列出各种吋能的局部解，通过决策保留那些冇可能达到最优的局部解，丢弃其他局部解。依次解决各子W题最后一个子W题就是初始W题的解。通过图的关系矩阵来表示各个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。关键字：货郎枳问题动态规划图矩阵目录1雜11.1内容简介11.2本次课设目的11.3课设内容22（此处用你的题目中的

5、重点研究部分名称代替）设计说明32.1程序设计过程详述32.2编程实现过程详述32.4原代码43实验研究小结73.1使用说明详述73.1.1本部分功能操作注意事项73.1.2本部分功能与其他系统的关系73.2测试案例详述8南犬101绪论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,怎样选择行走路线使总路程最短。W此，假设周游路线是开始于结点1并终止于结点1的一条

7、简单路径。每一•条周游路线都由一条边〈l,k〉和一条由结点k到结点1的路径所组成，其中k£V-{l};而这条由结点k到结点1的路径通过V-{1,k}的每个结点各一次。容易看出，如果这条周游路线是最优的，那么这条由k到1的路径必定是通过V-{1,k}中所宥结点的由k到1的最短路径，因此最优性原理成立。设（i,S）是由结点i釦及漾篇利札大璺课程设计(论文)用纸开始，通过S屮的所有结点，在结点1终止的一条最短路径长度。/(1,V-{1})是一条最优的周游路线长度。于是，可以得出Z(l,v-{1})=min{〜+g(k,V-{1,k})}2彡

8、k彡n一般化可得f(i,S)=min{co+貧(J,S-{j})}2(动态规划：货郎担问题算法设计与实现)设计说明2.1程序设计过程详述已知n个城巾*间距离，求从K7出发，经苏余城帘一次且仅一次最后返回的最短路径和距离。