《人工智能旅行商问题的求解方法》由会员分享，可在线阅读，更多相关《人工智能旅行商问题的求解方法（18页珍藏版）》请在金锄头文库上搜索。
1、旅行商问题的求解方法 摘 要：旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。关键词：旅行商问题；动态规划法；贪心法；分支限界法旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促
2、使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。一、 需求分析旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻
3、求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地TSP问题点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。旅行商问题要从图G的所有周游
4、路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!O( )。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。二、 总体设计1、最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。2、TSP问题最简单的求解方法是枚举法。它的解是多维的、
5、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。3、旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。4、TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP
6、成为一个知名且流行的问题。蜜蜂试验1、英国伦敦大学皇家霍洛韦学院等机构研究人员报告说，小蜜蜂显示出了轻而易举破解这个问题的能力。他们利用人工控制的假花进行了实验，结果显示不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。这可是首次发现能解决这个问题的动物，研究报告即将发表在美国博物学家杂志上。2、进行研究的奈杰尔雷恩博士说，蜜蜂每天都要在蜂巢和花朵间飞来飞去，为了采蜜而在不同花朵间飞行是一件很耗精力的事情，因此实际上蜜蜂每天都在解决“旅行商问题”。尽管蜜蜂的大脑只有草籽那么大，也没有电脑的帮助，但它已经进化出了一套很好的解决方案，如果能理解蜜蜂怎样做到这一点，对
7、人类的生产、生活将有很大帮助。1. 蛮力法蛮力法的设计思想：蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。在基本的数据结构中，一次处理每个元素的方法是遍历。2. 动态规划法动态规划法设计思想：动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次
8、求解，从而避免了大量重复计算。旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话,它只取其中的一个.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算.关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可能集合,动态
9、规划的递推关系为:gk(i,S)=mingk-1(j,Sj)+djij属于S,dji表示j-i的距离.或者我们可以用:f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路径.f(S,v)=minf(S-u,u)+dist(v,u)uinSf(V,1)即为所求3. 贪心法贪心法：贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。从问题的某一个初始解触发逐步逼近给定的目标，
10、以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下：1）建立数学模型来描述问题；2）把求解的问题分成若干个子问题3）对每一个子问题求解，得到子问题的局部最优解4）把子问题的局部最优解合成原问题的一个解贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。 从问题的某一初始解出发； while （能朝给定总目标前进一步） 利用可行的决策，求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解；4. 分支限界法分支限界法：假设求解最大化问题，解向量为，其中，的取值范围为某个有穷集合，。在使用
11、分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界down, up，然后从根结点出发，扩展根结点的个孩子结点，从而构成分量的种可能的取值方式。对这个孩子结点分别估算可能取得的目标函数值，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于，也就是部分解应满足： 三、 实现方法1. 蛮力法用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。如对于图1，我们求解过程如下：（1） 路径：1-2-3-4-1；路径长度：18；（2） 路径：1-2-4-3-1；路径长度：11；（3） 路径：1-3-2-4-1；路径长度：23；（4） 路径：1-3-4-2
12、-1；路径长度：11；（5） 路径：1-4-2-3-1；路径长度：18；（6） 路径：1-4-3-2-1；路径长度：18；从中，我们可以知道，路径（2）和（4）路径长度最短。我们还应注意到，图1中，有3对不同的路径，对每对路径来说，不同只是路径的方向，因此，可以将这个数量减半，则可能的解有（n-1）！/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速增长。如：一个10城市的TSP问题有大约有180,000个可能解。一个20城市的TSP问题有大约有60,000,000,000,000,000个可能解。 一个50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升
13、水。因此，我们可以知道用蛮力法求解TSP问题，只能解决问题规模很小的实例。2. 动态规划法假设从顶点i出发，令表示从顶点i出发经过中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，于是，TSP问题的动态规划函数为： 算法讨论：（1）for (i=1; iN; i+) /初始化第0列 di0=ci0; （2）for (j=1; j -1; j+) for (i=1; in; i+) /依次进行第i次迭代 if (子集Vj中不包含i) 对Vj中的每个元素k，计算Vm = Vj-k;dij=min(cik+dkm); （3）对V -1中的每一个元素k，计算Vm = V -1-k;d0
14、-1=min(c0k+dkm); （4）输出最短路径长度d0 -1;时间复杂性：和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。3. 贪心法贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。最近邻点策略：从任意城市出发，每次在没有到过的城市中选择距离已选择的城市中最近的一个，直到经过了所有的城市，最后回到出发城市。算法讨论1P= ; 2V=V-u0; u=u0; /从顶点u0出发3循环直到集合P中包含n-1条边
15、3.1查找与顶点u邻接的最小代价边(u, v)并且v属于集合V； 3.2 P=P+(u, v); 3.3 V=V-v; 3.4 u=v; /从顶点v出发继续求解时间复杂性但需注意，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。4. 分支限界法假设求解最大化问题，解向量为，其中，的取值范围为某个有穷集合，。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界down, up，然后从根结点出发，扩展根结点的个孩子结点，从而构成分量的种可能的取值方式。对这个孩子结点分别估算可能取得的目标函数值，其含义是以
