关于汉密尔顿最短路径的算法 　　赵禹骅1,任伟民1,李可柏2 　　(1.同济大学经济与管理学院,上海200092； 　　2.南昌大学理学院,南昌330047) 　　ArithmeticAbouttheShortestRouteofHamiltonLoop 　　ZHAOYu?hua1,RENWei?min1,LIKe?bo2 　　(1.TongjiUniv.,Shanghai200092；2.NanchangUniv.,330047) 　　Abstract：DiscussesanarithmeticabouthowtofindoutaHamiltonloop,whichpossessestheminimumtotalweight.Fromtheresultofanyclassicalarithmetic,thearithmeticcangetitspartialoptimization,soitimprovestheabilityofallclassicalarithmeticaboutHamiltonloop,Anditsworkloadcanbeexpressedaspolynomial. 　　Keywords：Hamiltonloop；Classicalarithmetic；Optimization；Polynomial 　　摘要：提出了一个对业已存在的赋权汉密尔顿回路进行优化的算法.该算法以经典算法的解为起点,寻找其局部极值点,极大改进了经典启发式算法的性能.该算法属半多项式算法.图8表1参2 　　关键词：汉密尔顿回路；古典算法；优化；多项式 　　1前言 　　1857年,英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题,其后,该问题进一步被发展成为所谓的“货郎担问题”,即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上著名的难题.而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例,如何使若干供货点的总运费最小,施工现场如何使供货时间最短等等,最终都归结为赋权汉密尔顿问题,是电站建设中成本控制和进度优化的关键技术；因而,赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题.而且,主生产计划安排,又可以分解为有向图的赋权汉密尔顿问题进行解决；因此,赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位,具有重大的理论和现实意义.理论上讲,赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中,枚举法的计算量巨大,对于n个点的问题存在(n－1)!条汉密尔顿回路,当n比较大时,枚举法显然是行不通的,为此,优化专家们提出了启发式算法[1],以期求得该问题的近似最优解.而不同算法之目的是共同的,即在多项式的运算量内,尽可能提高其解的精度.其中应用比较广泛的有Clarke和Wright的C－W算法,Norback和Love的几何算法[2],在此,称这些算法为经典启发式算法,简称经典算法,这些算法的一个共同特点就是非优化性.针对这一特点,本文提出一种局部优化的算法,对业已求得的汉密尔顿回路进行优化.这种算法的结果是以经典算法结果为起点的局部优化解,因此,该算法极大改进了经典启发式算法的性能,且在目前可考证的情况下,均能求得最优解；但是,是否在任何情况下都能求得最优解则尚待证明. 　　2算法及其特点分析 　　2.1算法思想的提出 　　所谓赋权汉密尔顿回路最小化问题是指,给定n个点及n个点两两之间的距离(或权数),求一条回路,使之经过所有的点,且经过每个点仅一次,而整条回路(也称路径或边界)的总距离(或总权数)最小. 　　这一问题总是可以通过枚举法求出其解的,但由于枚举法的计算量过大,达到(n－1)!的数量级,因而,不是可行的方法.由此,人们提出了启发式算法来求解问题的近似解.所谓启发式算法,一般地讲,就是发现某些最优解所具备的特征或不应具备的特征,对应有特征而言,求出含应有特征的可行解；对不应有特征而言,从解空间中剔除不应有特征的解,再从剩余空间中找一个解.因而,启发式算法可以定义为：从最优解的必要条件出发,设计一个有效算法,使之求出的解满足这些必要条件. 　　就一般算法的本质而言,它是提供一种规范的过程,经由该过程得出的解满足问题最优解的充分条件,即算法应该是问题最优解的充分条件的一种规范实现过程；而算法设计本身要求,算法必须给出解,因此,算法实际上还要满足最优解的必要条件,即算法可以定义为：算法是问题最优解的充分必要条件的一种规范实现过程. 　　启发式算法只满足了算法的必要性条件,而没有满足其充分性条件,就一般意义而言,其结果不是问题的最优解.基于这一思路,经典启发式算法的做法就是从满足必要条件的解空间中找出一个解,这就产生了一个问题：这样的解是否还可以按某种规则改进?这就涉及局部极值或重叠应用启发式算法的问题.如果存在局部极值或进一步优化的规则,那么,在已有解的基础上继续运用这些规则会极大改进算法的性能,这就是本算法的基本思路. 　　2.2算法的规则分析 　　依据上述局部优化的算法思想,对赋权汉密尔顿最小化问题进行分析.对该问题的一般形式(包括平面和非平面)给出一条规则：最优路径上各点在插入路径时,其路径变化量最小. 　　这是本文给出优化算法的基础.关于该规则,用反证法可以简单地证明,即若最优路径上有某一点在插入路径时,其路径变化量不是最小,那么,至少还有一种插入法的路径变化量更少,则以路径变化量更小的插法来代替原插入方法,由此形成的回路其路径更短,而这与原路径最短的假设矛盾,所以,规则成立. 　　依据上面的分析,给出相应的算法. 　　2.3算法 　　算法设计分为两步：(1)运用经典算法求出一条汉密尔顿回路；(2)运用本文算法对该回路进行优化.在此,不讨论由经典算法找出一条回路的方法,讨论依据上面原则对已有回路进行优化的算法. 　　2.3.1优化方法 　　第0步,确定一个初始的循环起点.即以汉密尔顿回路上的某一点作为循环的起点,以该起点为当前点,转入第1步. 　　第1步,跨线切割形成孤立点.即在已形成的汉密尔顿回路上,以当前点为跨线的起点,按路径方向作跨线,用跨线切割中间点,使该中间点成为孤立点,而该跨线成为一条边；此时,回路的路径上不包含全部点,故非然汉密尔顿回路,转入第2步. 　　第2步,将孤立点重新连入路径中.按路径变化量最小原则,将被切割下来的孤立点重新连入回路中；连入之后,回路的路径中包括全部点,故又形成汉密尔顿回路,转入第3步. 　　第3步,如果产生了路径的变化,则以新路径取代旧路径,但以原跨线的起点为循环的新起点,也为当前点,返回第1步,继续计算；否则,走向下一点,以下一点为当前点,转入第4步.