动态规划：货郎担问题算法设计与实现.docVIP

课程设计（论文） 课程名称： 系统优算法设计与实现 题 目： 动态规划：货郎担问题算法设计与实现 院 （系）： 管理学院 专业班级： 信管1501 姓 名： 学 号： 指导教师： 2017年 7 月 18 日 西安建筑科技大学课程设计（论文）任务书 专业班级： 信管1501 学生姓名： 指导教师（签名）： 一、课程设计（论文）题目 动态规划：货郎担问题算法设计与实现 二、本次课程设计（论文）应达到的目的 《》S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。 要求： 1．提交正确的和完整的程序设计代码。 2．提交设计说明书。 3. 接受现场检验。 四、应收集的资料及主要参考文献： 应收集的资料：本次设计应该收集和题目背景的有关资料。 主要参考文献： 1.胡运权.《运筹学》.清华大学出版社，2012 五、审核批准意见 教研室主任（签字） 设计总说明 货郎担问题（TSP问题）是指货郎要到n个城市售卖货物然后回到出发城市，要求各个城市经历一次且仅经历一次，并要求所走的路程最短。该问题又称为旅行商问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。动态规划算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。 本次课设运用动态规划解决货郎担问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题最后一个子问题就是初始问题的解。通过图的关系矩阵来表示各个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。 关键字：货郎担问题 动态规划 图 矩阵 目 录 1 绪论 1 1.1 内容简介 1 1.2 本次课设目的 1 1.3 课设内容 2 2 （此处用你的题目中的重点研究部分名称代替）设计说明 3 2.1 程序设计过程详述 3 2.2 编程实现过程详述 3 2.4 原代码 4 3 实验研究小结 7 3.1 使用说明详述 7 3.1.1 本部分功能操作注意事项 7 3.1.2 本部分功能与其他系统的关系 7 3.2 测试案例详述 8 参考文献 10 1 绪论 1.1 内容简介 货郎担问题(TSP)是指在城镇1~n中，已知各城市距离，货郎从城镇1出发，经过所有城镇一次，且仅一次，最后仍回到原出发的城镇1，应如何选择行路线可使总行程最短 1.2 本次课设目的 设计出算法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。从而求出货郎在1～n个城市中以第一个城市为起点走过n个城市并最终回到第一个城市的最短距离和路线。 1.3 课设内容 货郎担问题（也称TSP问题），其一般提法为：有n个城市，用1，2，…，n表示，城i,j之间的距离为cij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短。因此，假设周游路线是开始于结点1并终止于结点1 的一条简单路径。每一条周游路线都由一条边〈1,k〉和一条由结点k 到结点1 的路径所组成, 其中k∈V-{1} ; 而这条由结点k 到结点1 的路径通过V-{1 ,k}的每个结点各一次。容易看出, 如果这条周游路线是最优的, 那么这条由k 到1 的路径必定是通过V-{1, k}中所有结点的由k到1的最短路径, 因此最优性原理成立。设(i,S)是由结点i开始, 通过S中的所有结点, 在结点1终止的一条最短路径长度。f(1,V-{1}) 是一条最优的周游路线长度。于是, 可以得出 f(1,V-{1}) = min{c1k?+ g( k,V-{1,k})} ??2≤k