企业营销型网站团队,tomcat加jsp做网站,响应式网站有哪些2017,wordpress weex小智最近由于项目需要#xff0c;经常要接触到一些规划类的问题。那今天就给大家讲一讲旅行商问题及其解法吧。旅行商问题#xff0c;即TSP问题#xff08;Travelling Salesman Problem#xff09;。问题是#xff0c;有一个旅行商人要拜访n个城市#xff0c;每个城市只能… 小智最近由于项目需要经常要接触到一些规划类的问题。那今天就给大家讲一讲旅行商问题及其解法吧。旅行商问题即TSP问题Travelling Salesman Problem。问题是有一个旅行商人要拜访n个城市每个城市只能拜访一次而且最后要回到原来出发的城市。这位商人如何设计拜访顺序使走过的路径最短 这种求最短距离问题有非常多实际场景会涉及到比如快递公司为了使城市A到城市B的快递件运输速度达到最快他们会选择城市A到城市B的最短路径来进行运输。再比如游戏当中的角色移动时需要寻找到一条最短路径进行移动这样游戏中的角色才不会失真。又比如网络当中需要有路由算法用于计算最短的信息跳转路径。一款RPG游戏的角色移动演示你会发现角色走路沿最短路径。如果不这样设计游戏的体验感则会非常糟糕这么多实际的精彩案例旅行商问题确实值得研究而且学习完说不定能派上用场。对于这类问题我个人这次倾向使用动态规划算法来解这道问题得到他的精确解。动态规划这种技术也是有非常多实际场景会涉及到比如以动态规划为基础原理的维特比算法现今常用于语音识别这个领域。再比如生物信息学中需要进行DNA之间的比对找出最长的公共DNA部分。语音识别技术使得人机交互的难度不断下降其背后离不开数学这里首先讲解一下动态规划的步骤1、分段将原问题分解为若干个相互重叠的子问题。2、分析分析问题找出递推式。3、求解利用递推式自底向上计算实现动态规划过程。其实动态规划的精妙之处在于每个子问题只求解一次并将解保存在一个表格中当需要再次求解此子问题时只是简单地通过查表获得该子问题的解避免大量的重复计算。为了更好地在旅行商问题上讲解动态规划算法这里讲一个简单的例子隔壁村的老王要去这4座城市拜访城市之间的距离如下图。四座城市之间的距离示意图图中一共有4座城市城市0、城市1、城市2、城市3。小智目测走完这几个城市的最短路程为10城市0→城市1→城市2→城市3→城市0。人总是有直觉而且有时会非常准。当然我们要用科学而完整的方法而得到最短的拜访路径不能总是依赖直觉尽管直觉经常是对的。我们先用穷举法列一下所有路径这是暴力的穷举法一共需要运算3!×424次加法。暴力法是能得到结果但是时间复杂度是阶乘阶On!是算法当中复杂度极高的等级。常见的算法时间复杂度由小到大依次为常数阶Ο(1)对数阶Ο(logn)线性阶Ο(n)线性对数阶Ο(nlogn)平方Ο(n^2)立方阶Ο(n^3)…指数阶Ο(2^n)阶乘阶Ο(n!)。 从动态规划的角度看假如我们找到一条最短的路径城市0→城市1→城市2→城市3→城市0那么城市1→城市2→城市3→城市0必然是城市1到城市0的一条最短路径。假设该路径不是城市1到城市0的一条最短路径设该路径的总路程为d那么会有一条新的路径作为城市1到城市0的最短路径d’, d d’那么城市0→新路径→城市0为完成拜访的最短路径与原假设”找到一条最短路径城市0→城市1→城市2→城市3→城市0”矛盾。按照上述结论可以将路径进行分解。设最短路径的符号标记为 L。那么L(城市0→城市0) L(城市0→城市1) L(城市1到城市0)请注意城市0是起点城市和终点城市。假如已经获知各座城市到城市0的最短路径那么从城市0到城市0归结起来一共有三种路径L(城市0→城市1) L(城市1到城市0)L(城市0→城市2) L(城市2到城市0)L(城市0→城市3) L(城市3到城市0)在上述路径找到最短的路径即为拜访所有城市的最短路径。上述路径可以继续分解。比如以第1条路径为例L(城市1到城市0) L(城市1→城市2) L(城市2到城市0)就这样路径一直可以被分解到什么时候结束呢假设继续以上述的L(城市1到城市0)为例继续对L(城市2到城市0)进行分解L(城市2到城市0) L(城市2→城市3) L(城市3到城市0)由于城市1、城市2之前已经出现过了因此L(城市3到城市0)只能等于L(城市3→城市0)至此城市间的路径全部可以被分解。我们以符号来表达上述的过程。假设 d(i, V) 表示从城市 i经过城市集合 V各点一次后返回到出发点的最短距离。d(i, V) 可以按照一下方式分解其中Cki 为城市 k 到城市i 的距离。这样动态规划的递推式出来了。从城市0出发经过城市1、2、3后回到城市0的最短路径长度为这个是最后一个阶段的决策它必须依据 d(1, {2,3})、d(2, {1,3}) 和 d(3, {1,2})的计算结果继续分解当然还可以继续进行分解上述过程可以发现在计算的时候可以不断引用先前的计算结果这就是动态规划的特点。我们将上述过程在表格中把填写一下至此发现拜访完所有城市的最短距离为10印证了小智原来的想法。上述执行加法的次数时间复杂度为O(2n)。动态规划相比起穷举法下降了一个等级这个算法起到了重要的价值。完成原理阐述是时候写代码了先整理一下伪代码1、初始化一个表格d用于记录计算结果。并以距离初始化第0列2、循环j1:2n-1-1循环 i(1:n且不包含在V[j] 循环 V[j]中的所有元素 d[i][j] min(c[i,k], d[k][V[j]去掉k元素后对应的序号])3、计算d[0][2n-1-1] min(c[0,k] d[k][2n-1-2]此为最短路径长度这里需要注意的是集合V是从小变大要先算V较小的部分因此要找一个方式来表达集合V然后对计算进行顺序。这里将数字转换为二进制序列以表示集合V拥有的元素比如[1,0,0]可表示集合V只包含元素1[0,1,1]可表示集合V包含元素2和元素3。二进制数可以映射到自然数区比如0 →[0,0,0]、1 → [1,0,0]、2 → [0,1,0]、3 → [1,1,0]4 →[0,0,1]、5 → [1,0,1]、6 → [0,1,1]、7 → [1,1,1]为了实现集合从小到大的计算顺序对二进制序列进行特别的排序其中第一排序条件是序列的总和升序。第二排序条件是序列代表的数字升序转换为以下排序。这样按照上述表格中的序号作为顺序进行计算即可。可以动手编程了。我们挑一道更难的题目有10座城市的TSP问题另一道题目10座城市之间的距离矩阵有了想法很快就可以付诸实践了回复“TSP程序”可以获得程序这是最美妙的地方。按照上述流程最短路径距离为284最短路线0→3→1→5→7→6→2→8→4→9→0当然这个并不是一个完美的解法随着城市数量的增加计算难度呈指数增长目前关于TSP在多项式时间内的解法目前还没出现但我相信未来一定会诞生。
