锐客网

  1. 首页 > 生活百科 > >

旅行商问题python，急一道有关旅行商问题的计算机算法试题求助各位大虾

经验分享生活百科

1，急一道有关旅行商问题的计算机算法试题求助各位大虾图有些复杂 ， 从结点1开始进行遍历，画解空间树就可以 。
2 ， 计算机算法问题旅行商问题程序不写了，方法告诉你吧：先定义两个个数组 ， 一个存放城市之间的路程（费用），之后用循环，每次都选最少的一项 。用过的城市序号放到另一个数组里，做一个累加就可以了 。设状态变量是gk(i,s)..表示从0出发经过k个城市到达i的最短距离..s为包含k个城市的可能集合..动态规划的递推关系为: gk(i,s)=min[gk-1(j,s\{j})+dji] j属于s..dji表示j-i的距离设状态变量是gk(i,S)..表示从0出发经过k个城市到达i的最短距离..S为包含k个城市的可能集合..动态规划的递推关系为:gk(i,S)=min[gk-1(j,S\j属于S..dji表示j-i的距离
3 ， 请问我用lingo求解多旅行商问题要求从一个点出发最后回到起点lingo如果你安装的版本完整 应该可以在安装文件夹的sample里面找到一个lsp的例子 不过用lingo解这种问题如果比较复杂是很难解出的MODEL: ! Traveling Salesman Problem for the cities of Atlanta, Chicago, Cincinnati, Houston, LA,Montreal; SETS:CITY / 1.. 6/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY):DIST,! The distance matrix;X;! X( I, J) = 1 if we use link I, J; ENDSETS DATA:!Distance matrix, it need not be symmetric;DIST =0702454842 2396 11967020324 1093 21367644543240 1137 2180798842 1093 11370 1616 18572396 2136 2180 16160 29001196764798 1857 29000; ENDDATA !【旅行商问题python，急一道有关旅行商问题的计算机算法试题求助各位大虾】
4 ， 旅行商问题的问题分析旅行商问题要从图G的所有周游路线中求取最小成本的周游路线 ， 而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题 。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!>O( )) 。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!) 。枚举法思想：程序中采用深度优先策略 。（采用隐式和显式两种形式）枚举算法的特点是算法简单 ， 但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢 。如果枚举范围太大（一般以不超过两百万次为限） ， 在时间上就难以承受 。在解决旅行商问题时，以顶点1为起点和终点 ， 然后求为便于讨论 ， 介绍一些关于解空间树结构的术语 。在下面分析回溯法和分支限界法时都直接或间接用到解空间树 。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state） 。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space） 。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组 。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件） 。解空间的树结构称为状态空间树（state space tree） 。对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态 ， 接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出 。为了生成问题状态，采用两种根本不同的方法 。如果已生成一个结点而它的所有儿子结点还没有全部生成 ， 则这个结点叫做活结点 。当前正在生成其儿子结点的活结点叫E-结点 。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点 。在生成问题状态的两种方法中，都要用一张活结点表 。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点 。这相当与问题状态的深度优先生成 。在第二种状态生成方法中，一个E-结点一直保持到死结点为止 。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点 。如果旅行商问题要求找出全部解 ， 则要生成所有的答案结点 。使用限界函数的深度优先结点生成方法称为回溯法 。E-结点一直保持到死为止的状态生成方法称为分支限界法 。回溯法思想为了应用回溯法，所要求的解必须能表示成一个n- 元组(x1,…,Xn)，其中x1是取自某个有穷集Si 。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量 。假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P 。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解 。而回溯法的基本思想是 ， 不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解 。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去 。因此回溯法作的次数比硬性处理作的测试次数（m次）要少得多 。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显示约束和隐式约束 。分支限界法思想采用FIFO分支限界法 。如前所述，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法 。在总的原则下，根据对状态空间树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法 。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列） 。可以看出 ， 分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点 ， 尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点 。贪心法思想贪心法是一种改进了的分级处理方法 。它首先旅行商问题描述，选取一种度量标准 。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市 。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中 。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法 。获得最优路径的贪心法应一条边一条边地构造这棵树 。根据某种量度来选择将要计入的下一条边 。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边 。

    推荐阅读


    上一篇：ak102仁祥金属件上旋是什么,亚航ak102 是代表啥意思

    下一篇：苹果手机se3参数详细参数配置,se3什么时候上市的