动态规划：旅行售货员问题

《动态规划：旅行售货员问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、xxxxxxxx大学结课论文项目动态规划算法解决旅行售货商问题课程名称：xxxxxxxxxxxxxx院系：xxxxxxxxxxxxxx学生姓名：xxxxxx学号：xxxxxxxxx指导教师：xxxxxx2015年6月15日摘要：旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。动态规划（dynamicprogramming）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算

2、法或分治算法不能解决的问题。本次课程设计运用动态规划解决旅行售货员问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。通过图的关系矩阵来表示个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。关键字:旅行商问题动态规划法图矩阵目录第一章绪论1.1算法介绍1.2算法应用第二章动态规划理论知识2.1动态规划的基本思想2.

3、2动态规划设计步骤第三章旅行售货员问题3.1问题描述：旅行售货员问题3.2算法设计内容3.3算法分析3.4流程图第四章物流配送网络第五章结论第一章绪论1.1算法介绍动态规划（dynamicprogramming）是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。解决多阶段决策过程最优化问题，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是

4、：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。1.2算法应用动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题

5、时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决策过程分为离散决策过程和连续决策过程。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。第二章动态规划理论知识2.1动态规划的基本思想把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决

6、各子问题，最后一个子问题就是初始问题的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。2.2动态规划设计步骤1)划分阶段：按照问题的时间或空间特征，把问题分为若干阶段。这若干阶段一定要是有序的或可排序的（无后向性）。2)选择状态：将问题发展到各个阶段时所出现的各种客观情况用不同的状态来表示出来。状态的选择要有无后向性。3)确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。第三章旅行售货员问题3.1问题描述：旅行售货员问题某售货员要到若干城市去推销商品，已知各城市之间的路程。他要选定一条从驻地出发，经过每一个城市一遍，

7、最后回到驻地的路线，使总的路程最小，并求出最小路程。3.2算法设计内容不同城市的路线和距离都不一样。运用动态规划算法来设计本次课程设计，考虑到对问题进行阶段划分和状态的选择。使用Left函数实现V'-{k}的下标检索。根据遍历城市的各个阶段时所出现的情况并用不同的状态表示出来。当然这时的状态必须要满足无后向性。设计第一阶段则是各顶点为空，然后给赋值。依次遍历各城市，在TSP函数中得以实现。假设4个顶点分别用0、1、2、3