《关于汉密尔顿最短路径的算法》由会员分享，可在线阅读，更多相关《关于汉密尔顿最短路径的算法（8页珍藏版）》请在金锄头文库上搜索。
1、 地址：北京海淀闵庄路 3 号 清华科技园玉泉慧谷 电话：010-88856082 传真：010-88856082- 8008关于汉密尔顿最短路径的算法关于汉密尔顿最短路径的算法赵禹骅赵禹骅1 1，任伟民，任伟民1 1，李可柏，李可柏2 2(1.(1.同济大学经济与管理学院，上海同济大学经济与管理学院，上海 200092200092； 2.2.南昌大学理学院，南昌南昌大学理学院，南昌 330047)330047)Arithmeticrithmetic AboutAbout thethe ShortestShortest RouteRoute ofof HamiltonHamilton Loop
2、LoopZHAO Yuhua1，REN Weimin1，LI Kebo2(1.Tongji Univ.,Shanghai 200092；2.Nanchang Univ.,330047)AbstractAbstract：Discusses an arithmetic about how to find out a Hamilton loop,which possesses the minimum total weight.From the result of any classical arithmetic,the arithmetic can get its partial optimizat
3、ion,so it improves the ability of all classical arithmetic about Hamilton loop,And its workload can be expressed as polynomial.KeyKey wordswords：Hamilton loop；Classical arithmetic；Optimization；Polynomial摘摘 要：要：提出了一个对业已存在的赋权汉密尔顿回路进行优化的算法。该算法以经典 算法的解为起点，寻找其局部极值点，极大改进了经典启发式算法的性能。该算法属半多 项式算法。图 8 表 1 参 2
4、关键词：关键词：汉密尔顿回路；古典算法；优化；多项式1 1 前言前言1857 年，英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题，其后，该 问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个 问题成为数学史上著名的难题。而后者在工程优化、现场管理等现实生活中有重要作用： 以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等， 最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而， 赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。 而且，主生产计划安排，又可以分解为有向
5、图的赋权汉密尔顿问题进行解决；因此，赋权 汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现 实意义。理论上讲，赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中， 枚举法的计算量巨大，对于 n 个点的问题存在(n1)!条汉密尔顿回路，当 n 比较大时， 枚举法显然是行不通的，为此，优化专家们提出了启发式算法1，以期求得该问题的近似 最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。 其中应用比较广泛的有 Clarke 和 Wright 的 CW 算法，Norback 和 Love 的几何算法2， 在此，称这些算法为经典启发式算法
6、，简称经典算法，这些算法的一个共同特点就是非优地址：北京海淀闵庄路 3 号 清华科技园玉泉慧谷 电话：010-88856082 传真：010-88856082- 8008化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的汉密尔顿回路进行优 化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经 典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情 况下都能求得最优解则尚待证明。2 2 算法及其特点分析算法及其特点分析2.12.1 算法思想的提出算法思想的提出所谓赋权汉密尔顿回路最小化问题是指，给定 n 个点及 n 个点两两之间的距离(
7、或权 数)，求一条回路，使之经过所有的点，且经过每个点仅一次，而整条回路(也称路径或边 界)的总距离(或总权数)最小。这一问题总是可以通过枚举法求出其解的，但由于枚举法的计算量过大，达到(n1)!的 数量级，因而，不是可行的方法。由此，人们提出了启发式算法来求解问题的近似解。所 谓启发式算法，一般地讲，就是发现某些最优解所具备的特征或不应具备的特征，对应有 特征而言，求出含应有特征的可行解；对不应有特征而言，从解空间中剔除不应有特征的 解，再从剩余空间中找一个解。因而，启发式算法可以定义为：从最优解的必要条件出发， 设计一个有效算法，使之求出的解满足这些必要条件。就一般算法的本质而言，它是提供
8、一种规范的过程，经由该过程得出的解满足问题最 优解的充分条件，即算法应该是问题最优解的充分条件的一种规范实现过程；而算法设计 本身要求，算法必须给出解，因此，算法实际上还要满足最优解的必要条件，即算法可以 定义为：算法是问题最优解的充分必要条件的一种规范实现过程。启发式算法只满足了算法的必要性条件，而没有满足其充分性条件，就一般意义而言， 其结果不是问题的最优解。基于这一思路，经典启发式算法的做法就是从满足必要条件的 解空间中找出一个解，这就产生了一个问题：这样的解是否还可以按某种规则改进?这就 涉及局部极值或重叠应用启发式算法的问题。如果存在局部极值或进一步优化的规则，那 么，在已有解的基础
9、上继续运用这些规则会极大改进算法的性能，这就是本算法的基本思 路。 2.22.2 算法的规则分析算法的规则分析依据上述局部优化的算法思想，对赋权汉密尔顿最小化问题进行分析。对该问题的一 般形式(包括平面和非平面)给出一条规则：最优路径上各点在插入路径时，其路径变化量 最小。这是本文给出优化算法的基础。关于该规则，用反证法可以简单地证明，即若最优路 径上有某一点在插入路径时，其路径变化量不是最小，那么，至少还有一种插入法的路径 变化量更少，则以路径变化量更小的插法来代替原插入方法，由此形成的回路其路径更短， 而这与原路径最短的假设矛盾，所以，规则成立。依据上面的分析，给出相应的算法。 2.32.
10、3 算法算法算法设计分为两步：(1)运用经典算法求出一条汉密尔顿回路；(2)运用本文算法对该 回路进行优化。在此，不讨论由经典算法找出一条回路的方法，讨论依据上面原则对已有 回路进行优化的算法。 2.3.1 优化方法第 0 步，确定一个初始的循环起点。即以汉密尔顿回路上的某一点作为循环的起点， 以该起点为当前点，转入第 1 步。第 1 步，跨线切割形成孤立点。即在已形成的汉密尔顿回路上，以当前点为跨线的起地址：北京海淀闵庄路 3 号 清华科技园玉泉慧谷 电话：010-88856082 传真：010-88856082- 8008点，按路径方向作跨线，用跨线切割中间点，使该中间点成为孤立点，而该跨
11、线成为一条 边；此时，回路的路径上不包含全部点，故非然汉密尔顿回路，转入第 2 步。第 2 步，将孤立点重新连入路径中。按路径变化量最小原则，将被切割下来的孤立点 重新连入回路中；连入之后，回路的路径中包括全部点，故又形成汉密尔顿回路，转入第 3 步。第 3 步，如果产生了路径的变化，则以新路径取代旧路径，但以原跨线的起点为循环 的新起点，也为当前点，返回第 1 步，继续计算；否则，走向下一点，以下一点为当前点， 转入第 4 步。第 4 步，判断一个循环是否完成，即当前点是否是循环的起点。如是，则算法结束； 如不是，则转入第 1 步。(算法描述完毕)当算法结束时，回路上的每一个点相对于其它点都
12、是最优，即回路达到其局部极值。对平面问题，为简化计算，当跨线为内连线时，不作变动，向下一点走；当跨线为外 连线时，切割其中间点，然后再将被切掉的中间点重新连入路径中。 2.3.2 几个概念跨线：在回路中，连线两个不相邻点，且中间只有一个点，这个中间点是该连线的起 点和终点的相邻点，该连线称跨线。例如，在回路 ABCDEFGA 中，A 与 B、B 与 C 等都是相邻点，则连线 AC 连接了不相邻点 A 和 C，且其中间只有一个点 B，而点 B 是 A 的相邻点，也是 C 的相邻点，故连线 AC 是跨线。边：两个相邻点之间的连线，如上面 A 与 B 的连线，B 与 C 的连线都是边。路径变化量：将
13、某一点连入路径中，就是要把该点与路径中的某一条边的起点和终点 相连，以这两条新的边取代原来的边；这样，新的两条边长(权重)之和与原来边长(权重) 的差就是将该连入路径后引入路径长(总权重)的变化量，称路径变化量。例如，将点 D 插 入回路 ABCEFGA 的边 EF 中，实际上就是将 ED 和 DF 相连，用新的边 ED 和 DF 取代原来的边 EF，由此引起的路径变化量，即回路 ABCEFGA 与回路 ABCEDFGA 的总长度(总权重)之差等于两条新边的长度(权重)之和减原来边 的边长(权重)，即等于 EDDFEF。路径变化量最小原则：从上面路径变化量的定义可以看出，将一个点插入路径中，可
14、 以有多条边供选择，而插入不同的边，所引起的路径变化量各不相同；但其中有一条边， 当将要插入的点插入该边时，其路径的变化量最小，则选择将该点插入该边。下面将运用一个实例来对算法进行更详细的说明。3 3 实例实例给定问题如图 1 所示，求过点 A，B，C，D，E，F，G，每个点仅一次的回路，且其路 径要最短。上述七点两两之间的距离如表 1。 3.13.1 运用经典算法求出一条回路运用经典算法求出一条回路在此选用 Clarke 和 Wright 的 CW 算法求得。回路：ABCFEDGA，如图 2 所示；地址：北京海淀闵庄路 3 号 清华科技园玉泉慧谷 电话：010-88856082 传真：010
15、-88856082- 8008至此，经典启发式算法对赋权汉密尔顿问题的求解过程结束。在此基础上，进一步对 路径进行优化，以该解为起点，寻找其局部极值。 3.2 对业已形成的赋权汉密尔顿回路进行优化(1)由图 2 从 A 点开始作第 1 次循环调整此时，循环起点 T=A，当前起点 S=A，当前图标号 N=2。(2)图 2 中，由 S=A 点作跨线 AC，AC 是内连线，不切割点。向下点走，S=B。(3)图 2 中，由 S=B 点作跨线 BF，BF 是内连线，不切割点。向下点走，S=C。(4)图 2 中，由 S=C 点作跨线 CE，CE 是外连线，切割 F 点，得图 3。按规则（路径变 化量最小原则）重新将点 F 插入路径中，计算 F 的路径变化量如下：因 C 点跨线引起了路径变化，所以，T=C，且应对新图再从 S=C 点继续作跨线。由图 4，跨线为 CD，CD 是外连线，切割 E 点，得图 5。按规则重新将点 E 插入路径中。计算 E 的路径变化量如下。地址：北京海淀闵庄路 3 号 清华科技园玉泉慧谷 电话：010-88856082 传真：010-88856082- 8008则 E 点的最小路径变化量为：DEF=0.31。所以，将点 E 插入边 DF 中，得图 6，N=6。因 C 点跨线引起路径变化，所以，T=C，图 6 中，再从 S=C 点继续作跨线。图
