什么是汉密尔顿回路问题?（哈密尔顿）

什么是汉密尔顿回路问题?（哈密尔顿）
什么是汉密尔顿回路问题?（哈密尔顿）

什么是汉密尔顿回路问题?（哈密尔顿）
关于汉密尔顿最短路径的算法
赵禹骅1,任伟民1,李可柏2
(1.同济大学经济与管理学院,上海 200092；
2.南昌大学理学院,南昌 330047)
Arithmetic About the Shortest Route of Hamilton Loop
ZHAO Yu?hua1,REN Wei?min1,LI Ke?bo2
(1.Tongji Univ.,Shanghai 200092；2.Nanchang Univ.,330047)
Abstract：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 optimization,so it improves the ability of all classical arithmetic about Hamilton loop,And its workload can be expressed as polynomial.
Key words：Hamilton loop；Classical arithmetic；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步.
第4步,判断一个循环是否完成,即当前点是否是循环的起点.如是,则算法结束；如不是,则转入第1步.(算法描述完毕)
当算法结束时,回路上的每一个点相对于其它点都是最优,即回路达到其局部极值.
对平面问题,为简化计算,当跨线为内连线时,不作变动,向下一点走；当跨线为外连线时,切割其中间点,然后再将被切掉的中间点重新连入路径中.
2.3.2 几个概念
跨线：在回路中,连线两个不相邻点,且中间只有一个点,这个中间点是该连线的起点和终点的相邻点,该连线称跨线.例如,在回路A－B－C－D－E－F－G－A中,A与B、B与C等都是相邻点,则连线AC连接了不相邻点A和C,且其中间只有一个点B,而点B是A的相邻点,也是C的相邻点,故连线AC是跨线.
边：两个相邻点之间的连线,如上面A与B的连线,B与C的连线都是边.
路径变化量：将某一点连入路径中,就是要把该点与路径中的某一条边的起点和终点相连,以这两条新的边取代原来的边；这样,新的两条边长(权重)之和与原来边长(权重)的差就是将该连入路径后引入路径长(总权重)的变化量,称路径变化量.例如,将点D插入回路A－B－C－E－F－G－A的边EF中,实际上就是将ED和DF相连,用新的边ED和DF取代原来的边EF,由此引起的路径变化量,即回路A－B－C－E－F－G－A与回路A－B－C－E－D－F－G－A的总长度(总权重)之差等于两条新边的长度(权重)之和减原来边的边长(权重),即等于ED＋DF－EF.
路径变化量最小原则：从上面路径变化量的定义可以看出,将一个点插入路径中,可以有多条边供选择,而插入不同的边,所引起的路径变化量各不相同；但其中有一条边,当将要插入的点插入该边时,其路径的变化量最小,则选择将该点插入该边.
下面将运用一个实例来对算法进行更详细的说明.