本文主要为广大网友提供“调整测试向量中最小的测试应用时间TSP问题研究”，希望对需要调整测试向量中最小的测试应用时间TSP问题研究网友有所帮助，学习一下!
5. TSP算法 5.1 TSP概念 旅行商问题(Traveling Salesman Problem ，简称TSP)描述如下。已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后必须返回出发城市。如何安排这些城市的访问次序，可使其旅行路线的总长度最短。这个问题可分为对成旅行商问题和非对称旅行商问题。旅行商问题是一个典型的组合优化问题，并且是一个n级难问题，其可能的路径数目和城市数目n是成指数型增长的，所以一般很难精求出最优解。 旅行商问题是一个典型的NP-完全问题，它也是图论中一个很著名的问题，它之所以著名有两方面的原因:一是实际中有很多应用问题都可以归结或转化为旅行商问题;二是由于旅行商问题的难于求解性，特别是对规模较大的问题，从而吸引了许多有志者从事其有效求解算法的研究。为了便于理解，我们先给出现实中旅行商问题的两个例子，然后再给出一般性概念。例如,幼儿园巴士问题:某一幼儿园，有n个小朋友，幼儿园有一辆巴士负责每天接送他们上下学，问如何安排行车路线，才使每天的耗油量最少。再如，集成电路制造问题:在一块集成电路板上，往往容纳成千上万的电子元件，在制造集成电路的过程中，从一个元件移动到另一个需要消耗一定的能量，问如何安排制造的顺序，才能使所消耗的能量最少。以上两个问题虽然涉及不同的领域，但它们存在着共同的特征，抓住问题的本质，并代替用图论之术语，旅行商问题的一般概念是:给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图Cr-(V, A)，其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路。 5.2 TSP问题的基本性质 为了更加细致而深入的探讨旅行商问题，这里我们研究一下旅行商问题的基本性质。首先看一下它的分类。按照TSP路径关系的不同特征，通常有以下两种基本分类： (1) 任意两个城市之间来回路径均相等或可以不相等，这可以归结为无向图或有向图问题。 (2) 任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单行路径，这可以归结为完全图或者非完全图问题。将以上两种情形加以组合，可以得到以下四种TSP的路径关系: (1) 完全有向图; (2) 完全无向图: (3) 非完全有向图; (4) 非完全无向图。 而在大量的TSP文献中上述分类仅被表述为对称TSP和非对称TSP,我们认为只用对称性来描述TSP是过于简单的。还可以按空间位置特征作如下两种分类; (1) 具有邻接路径关系的TSP 在这种类型中，各个城市之间的路径具有明显的地域性限制，如果某城市在与之相邻的城市一边:则不能跨越这个城市与该城市另一边的相邻城市建立直接的路径关系，例如各城市间的公路网。即问题是“平面”的，由此构成的路径矩阵往往具有“稀疏矩阵”的特点。 (2) 具有随机路径关系的TSP 这种类型中，任意两个城市之间均可以存在路径，路径关系是随机的，不受地域限制，例如飞机的航线，即问题是“立体”的。当然，按照空间位置特征所作的分类(1)可归属于非完全图类，而(2)可归属于完全图类。这种分类方式只是强调了实际应用。讨论完旅行商问题的分类，我们再具体看一下它的难解性。前面己经提到,旅行商问题是一个典型的NP-完全问题。 5.3 LKH实现 两级是N级TSP算法的一个特例，每一步，为了得到更短的路径，可能需要重新排列这N条路径。而当结点数量越多，这种算法的结果可能更加优化。不幸地是，当结点数量增加时,时间复杂度变高，所以，如何权衡精确度和时间成了这种算法的一个难题。但是，两位外国学者通过使用不同的优化算法解决了这个难题。这个算法在运行时改变的值，在每次迭代时生成最合适的值。在每一个迭代步骤，算法会检测是否当前的N值有利于找到一条更短的路径。假定已经给定了r链路的最短路径序列，一系列的测试会用来决定条r+1路径的位置。这个过程一直循环下去直到满足结束的条件。 Lin 和 Kernighan 原来的算法理论上十分有效。对于50个城市规模的问题，一次计算找到最优解的几率接近100％。但是对于100个城市规模的问题，可能一下降到20％到30％。但是，通过增加几次计算，还是能很快找到最优解。 |
| 本站发布的计算机毕业设计均是完整无错的全套作品，包含开题报告+程序+论文+源代码+翻译+答辩稿PPT |
本文选自计算机毕业设计http://myeducs.cn
|
