HybridHAM：一种新型混合启发式为查找哈密顿周期

抽象

哈密顿循环问题是研究最多的组合问题之一。作为一个NP完全问题，启发式方法比指数时间精确算法更为强大。本文提出了一种介于复杂可靠方法和简单快速方法之间的高效混合启发式算法。该算法是贪婪、旋转变换和不可达顶点启发式算法的结合，分三个阶段工作。在第一阶段，使用贪心深度优先搜索创建初始路径。然后利用旋转变换和贪婪深度优先搜索将初始路径扩展到第二阶段的哈密顿路径。第三阶段利用旋转变换将哈密顿路径转化为哈密顿循环。该方法可以从文献中收集的一组硬图、TSPLIB中给出的所有哈密顿实例（1000到5000个顶点）以及FHCP挑战集的一些实例中找到哈密顿圈。此外，该算法具有O（n³）最坏情况下的时间复杂度。该算法的性能已与国家的最先进的算法进行比较，发现HybridHAM优于他人在运行时间方面。

一。介绍

哈密顿循环问题(HCP)是在一个无向图中识别一个循环，这个无向图连接图中的所有顶点。它被认为是最流行的np完全问题，旅行商问题(TSP)的子问题，其中的问题是找到最小加权哈密顿循环。哈密顿循环有很多应用，比如重建基因组序列，解决伊柯赛类游戏，在棋盘上寻找骑士之旅，以及为正则图寻找圆形嵌入。到目前为止，还没有一种有效的算法来解决这个问题。目前的算法主要分为指数时间穷举搜索算法和多项式时间启发式算法。第一类保证提供解决方案，而后者则不保证。与前者相比，后者在大多数情况下都能在更短的时间内给出解决方案。第一类算法通常会找到一些有效的剪枝规则，以减少搜索空间，从而提高运行时间，而第二类算法会找到一些通用的重击规则，以在尽可能多的问题实例中以更少的时间找到解决方案。本研究的目的是设计一种启发式，它比已建立的复杂启发式更快，但比非常快的技术更可靠。

文献中有许多定理，给出了充分必要的条件[1-4]哈密顿循环。这些条件用于检查图是否是哈密顿图。好的学习[五]在这些定理和求解算法HCP通过Vandegriend＆罗勒给出。鲁宾和弗兰克[6]提出查找以定向或无向图的所有汉弥尔顿路径或周期的穷举搜索方法。Christophides [7提出了一种多路径算法，又与指数复杂的智能搜索算法。Christophides算法已被Kocay与威廉[改善8通过提出两个精简搜索空间的操作。圆形石堡(9提出了一种使用低次优先启发式选择下一个顶点的回溯搜索算法。Ejov等[10]通过求解从图的邻接矩阵得出的方程来求解HCP。即使在非哈密顿图的情况下，它们也能找到长周期，但它们不能降低指数时间复杂度。Posa算法[11]被认为是用于对HCP的启发式算法的基础算法。旋转变换的波萨那的想法和它的变体形成的几乎所有的启发式算法后提出的基础。Angluin和忠烈[12]由于旋转变换不适用于有向图，提出了一种更为复杂的有向图变换。Bollobas等人。[13]提出了一种利用旋转变换和循环扩张的HAM循环算法。各种版本的HAM算法，如SparseHam[14]和HideHam [15]也提出了不同类型的图形。Brunacci [16]提出两种算法DB2和DB2A，其考虑作为HCP和版本TSP的nonedges为高度加权边缘。DB2A算法是DBA算法的有向图，其中有向图被转换成无向图的变形例。许多TSP启发，如著名的林Kernighan启发式算法[17，18]使用称为“K-OPT”转化技术[19，20.]，其是k条边的交换。Baniasadi等。[21受k-opt变换的启发，提出了一种求解HCP的“蛇和梯子”启发式算法。很少有已发表的HCP启发式位于复杂可靠启发式和非常简单(通常是线性或二次时间)方法之间的“中间”区域。

所提出的启发式是贪心深度优先搜索，不可达的顶点，和旋转变换的启发式的组合。贪婪的深度优先搜索大大降低了运行时间。搜索是贪婪的，因为它总是选择未访问的低度顶点用于扩展的路径。虽然可达顶点启发式减少到达死胡同的机会，旋转变换帮助来死胡同条件的出来。因而所提出的方法比复杂的精确算法比更快启发式更快和更可靠。

2。材料和方法

2.1。哈密​​顿环问题

哈密顿循环是一个仅连接给定图中所有顶点一次的循环。包含至少一个哈密顿环的图称为哈密顿图。这个优化问题可以形式化地定义如下：

给定图G =（E，V），其中，E是一组曲线图的边，V是该组中的图的顶点和 。

问题是要找到一个周期，HC =（V₁,v₂,………,），其中所有（ ）和（ )是E的元素。

这是一个很难的问题，吸引了数学家和计算机科学家。它被认为是NP完全问题的强有力的代表之一。

2.2。贪婪的深度优先搜索

该HCP的大搜索空间可以探讨任何明智的广度和深度明智的。在深度优先搜索，搜索是在深度明智的方式进行从一个给定的顶点为止的点开始，其中搜索无法继续进行，或者达到了死胡同。所提出的启发式用途贪心深度优先搜索创建哈密尔顿路径。路径从建设程度最高的顶点开始，因为它增加了返回到起始顶点的概率。一个顶点的程度是连接到该顶点的边的数量。路径的另一顶点通过选择未访问的邻居中最小程度的邻居贪婪地选择。最低程度的顶点首先添加到路径，因为它们可能会变得无法访问与邻国的选择。例如，如果一个顶点的程度是2则该顶点的两个边缘必须存在于汉弥尔顿路径/周期和这些边被添加到路径的第一。这是路径的一部分顶点构建到目前为止被认为是“拜访”。由于汉密尔顿的周期顶点只出现一次，只有当前顶点需要未访问的邻居被考虑。 In order to guide the greedy depth first search further to longer paths, an unreachable vertex heuristic is proposed. According to this heuristic, before adding a vertex to the path, an unreachable condition is checked for each of its neighbours. This heuristic is explained in Section2.3。

2.3。不可达顶点启发式

这项研究提出了一种新的启发，即不可达的顶点启发，减少达到了死胡同，而构建汉弥尔顿路径的机会。

定义1。设P为部分路径和X是局部的路径上的结束点。选择下一个顶点ÿ∈Adj(x)在路径中，使所有的j(y)顶点的未访问邻接顶点的数目大于1。

顶点是说，如果所有的邻居都已经到目前为止构建的路径的一部分为不可达。在这种情况下，没有办法达到顶点，它变得无法访问。在此提出的启发式，如果一个顶点的选择作出任何其未访问的邻居不可达，然后该顶点将不会被添加到路径。

例如，考虑图中所示的图1。

设目前确定的部分路径为A→C→D。在给定的图中 。设下一个选定的顶点为E。 。B，G和F的未访问的邻居的数目分别是1,2和2。根据不可达顶点启发式，E将不被选择为下一个顶点的路径，因为B的未访问的邻居的数量是一个。

2.4。旋转变换

旋转变换[11而它的变化被发现是发现哈密顿循环的强大启发。它用于改变路径以获得一个新的端点，如图所示2。在图中，e是在其上旋转变换施加到得到一个新的端部顶点的端部。

旋转变换的步骤，总结如下。（1）在输入图中找到一个与e相邻的顶点，在路径P中。设它为顶点b。（2）创建一个新的路径P”，（一个）通过连接B至E（b）中通过从C反转到E的路径

该算法，旋转变换用于两个目的。（1）为了哈密顿路的建设过程中来死胡同了。（2）把哈密顿路径转换成哈密顿循环。

在第一种情况下的路径的最高程度端被选择用于旋转变换，因为其增加得到一个新的端部的可能性。类似地，用于将路径转换周期中，通道的最低的程度端顶点被选择用于旋转变换，因为其增加返回到较高程度的结束，使循环的概率。

3.提出的混合启发式

3.1。HybridHAM算法

提出的混合算法分三步工作：（1）创建初始路径（2）转换为哈密尔顿路径的初始路径。（3）转换为哈密顿圈哈密顿路径。

3.1.1。初始路径创造

从程度最高顶点的路径创建开始，然后将最小程度的顶点贪婪，以构建初始路径尽可能长的时间。度最高初始顶点，然后最小程度的顶点的选择是为构建一个较长的初始路径，并在表中所示1。该算法在路径添加顶点之前检查不能到达条件。这是为了减少道路施工期间达到一个死胡同的概率。如果有一个以上程度最高的顶点，然后通过选择作为起始顶点他们中的每一个重复创建初始路径的这个程序，并选择与顶点作为初始路径的最大数量的路径。按照此过程中，我们可能会是哈密顿或接近汉密尔顿的初始路径。

3.1.2条。初始路径到哈密顿路径的转换

如果创建的初始路径不是哈密顿（顶点数小于顶点总数），则选择初始路径的最高阶末端进行旋转变换。这是为了增加获得新端点的概率，以便进一步扩展路径以创建哈密顿路径。按照第节中的贪婪过程从新的端点扩展路径3.1.1。旋转变换和贪婪的路径扩展一直持续到我们得到一个哈密顿路径。在在此过程中的任何时间，旋转变换无法应用意味着该图不是具有汉弥尔顿路径或算法未能识别汉弥尔顿路径。

3.1.3。哈密​​尔顿路径转化为哈密顿周期

如果汉弥尔顿路径的两端连接在图中的边那么边缘添加到路径得到汉密尔顿的周期。否则，应用旋转变换到最小的程度顶点，直到获得可连接到另一端顶点以形成哈密顿周期一个新的端部顶点。在在此过程中的任何时间，旋转变换无法应用，意味着该图不是具有哈密顿周期或算法未能识别汉密尔顿的周期。

在各个步骤中使用的顶点选择标准总结在表1。

3.2。例

考虑图中的无向图3。

3.2.1。在步骤1中鉴定的最初路径

0 1 2 3 4 5 6 7 8 12 13 14 22 21 20 19 18 15

这里初始路径的长度是18，小于图中顶点的总数。由于确定的路径不是哈密顿函数，转到步骤2。

3.2.2。在步骤2中识别哈密顿路径

0 7 8 12 14 13 15 17 16 9 1 2 3 4 5 6 11 23 22 21 20 18 19 10

这里路径的长度是24，因此它是哈密顿路径。因为身材没有优势3中，连接路径的端部的顶点（即，边缘连接顶点1及顶点11），去到步骤3并应用旋转变换，发现被连接在图中图的新的结束顶点3

3.2.3条。步骤3中确定的哈密顿循环

0 7 8 12 14 13 15 16 17 18 19 20 21 22 23 11 6 5 4 10 3 2 9 1

这里顶点1和2的端部被连接在图中所示的初始图3因此形成汉密尔顿的周期。它示于图4。

3.3条。伪码

算法的输入是图的邻接矩阵表示，输出是对应于哈密顿循环的顶点集。让是图中顶点的数目。该算法包含三个阶段，并概述如下：

HybridHAM ()

从输入邻接矩阵，创建两个阵列和分别在他们的学位的增加和减少的顺序排序，顶点。

//阶段1

//创建一个初始路径（1）从最高程度顶点（第一阵列中的顶点中的一个开始)。随它去 。（2）将它添加到初始路径 。（3）重复（一个）选择下一个最小度数的邻居(从数组中)。随它去 。（b）中如果选择不会让任何未经探视的邻居无法接近（一）它添加到初始路径(2)使如

直到变成了死胡同。

//第1阶段结束（4）如果 然后转到第3阶段。其他对图的每个最高阶顶点重复第1阶段，并选择最长P_一世作为初始路径。如果

//阶段2

//转换初始路径成汉弥尔顿路径（5）重复（一个）选择路径度最高的结束为旋转变换（b）中反向如果第一个顶点是有程度比上一次更高的顶点，使度最高的顶点作为路径的结束点。随它去 。（三）应用旋转变换到运用找到一条新路。（四）如果不能应用旋转变换，那么要么是图不具有哈密顿路径，要么是算法无法识别哈密顿路径而退出。（五）通过使用贪心深度优先搜索在第一阶段延长这条新道路。直到 。（6）现在是哈密顿路径吗 。分配 。

// 2阶段结束(7)如果连接的第一个和最后一个顶点的边缘在图中，则 是哈密顿循环和返回其他的进入第3阶段如果

//第3阶段

//将哈密顿路径转换为哈密顿循环(8)重复（一个）选择路径的最小度结束为旋转变换（b）中反向如果第一个顶点具有比最后一个顶点高的度，使最小度顶点成为路径的结束顶点。随它去 。（三）应用旋转变换到运用找到一条新路。（四）如果旋转变换不能然后或者应用的图不是具有Hamilton回路或算法未能识别汉弥尔顿路径等退出。直到有连接路径的第一和最后一个顶点边缘 。(9)现在是哈密顿循环和返回 。

//第3阶段结束

// HybridHAM算法完

3.4条。最坏情况复杂性

（1）有序阵列的创建T（n）=O（n²）（2）阶段1最坏情况下，贪心深度优先搜索遍历邻接矩阵一次，复杂度为O(n²)。对于每个最高次的顶点都要重复这种搜索。最坏的情况是顶点都是一样的程度。因此，T（N）= O（N³）（3）阶段2在最旋转变换的复杂度为O（n）的贪心深度优先搜索的复杂性为O（n²）这两个的总和等于O(n²）这两个操作最多重复一次时代。因此，T（N）= O（N³）（4）第3阶段在最旋转变换的复杂度为O（n）的重复此操作最多时代。因此，T（N）= O（N²）

HybridHam，T（n）的总最坏情况下的复杂性= O（N²）+ O（N³)+ O (n³)+ O (n²)=O（ )。

四。实验

在4GB内存和Intel-Core i5处理器的系统中进行了性能评估实验。算法在MATLAB 13RA中实现。实验是在从文献和TSPLIB收集的一组图上进行的。

4.1条。样本哈密顿循环图

由所提出的算法对所收集的一组样品的曲线图的所返回的哈密顿循环显示于图五。

解决这些样品实例的算法的运行时间在表中给出2。

4.2。TSPLIB实例

TSPLIB图书馆[22]包含的1000，2000，3000 7分哈密顿圈的情况下，和5000米的顶点。该算法可以解决在几秒钟所有这些问题的实例。该算法的运行时间与比较HCP求解器[23]，协和TSP求解器[24]，以及最新的蛇和梯子启发式[21]。表3给出由这些算法来解决每个HCP实例的所花费的时间。

4.3。FHCP挑战设置

该FHCP挑战集[25]是1001个哈密顿环问题实例的集合。此数据集是专门设计用来抵御启发式方法。HybridHAM是在FHCP挑战组的250个实例进行测试。这些250个实例，所提出的启发式可以找到75条汉弥尔顿路径和6个哈密顿周期。完整的结果示于表4。该图是过于稀疏，这样旋转变换无法把汉弥尔顿路径到汉密尔顿的周期在算法的第三阶段。阶段1并且该算法的第2阶段进行比较以及与所述挑战集的高难实例，因此汉弥尔顿路径。研究还发现，所提出的最高程度和最小程度的顶点选择标准适应具有不同程度的顶点更多图表。然而，该算法可以找到从介质稀疏图哈密顿周期在很短的时间（例如，图形72，79，84，90等表4). 即使是赢家[26]他们对不同类型的图使用不同的算法，因为他们的目标是寻找解决方案，而不是开发算法。

这将是值得指出的是数据集是非常罕见的，难以构建FHCP挑战困难的情况下，更何况遭遇“自然“。另外，即使发现了一个哈密顿路径是困难的（NP完全）问题和提出的启发式成功这样做的FHCP挑战集的多个实例。

五，结论

本文提出了一种由无向图发现汉密尔顿的周期混合启发。所提出的三阶段算法使用三个试探法的组合：贪婪深度优先搜索，不可达的顶点，和旋转变换。从可变大小和复杂性的不同的图表进行的各种实验，发现用于选择初始顶点对用于转化的创建最长初始路径的以及汉弥尔顿路径和最小程度启发式程度最高的启发式以哈密顿圈哈密顿路是获得在一次运行该解决方案的原因。实验评估也表明，提出的启发式更快，在大多数情况下，取得了良好的效果成功。它应该是值得一提的是，在速度的提高是在不牺牲对各种尺寸（包括相当大TSPLIB实例）的“易”情况下，启发式的可靠性和它仍然表现相当不错更加困难的情况下。

数据可用性

支持这项研究的数据来自先前报告的研究和已被引用的数据集。处理后的数据在[22，25].

利益冲突

作者宣称没有利益冲突。

致谢

在这个手稿中提出的研究是由大学拨款委员会重大项目资助F.No.42-136 / 2013（SR）的支持。

工具书类

1. G. A.狄拉克，“抽象图形的几个定理”伦敦数学学会学报。第三系列卷。2，第69-81，1952年。查看在：出版商网站|谷歌学术|MathSciNet
2. 澳矿，“注意汉密尔顿电路”美国数学月刊，第67卷，55页，1960年。查看在：出版商网站|谷歌学术|MathSciNet
3. G、 范，“图中循环的新充分条件”组合理论杂志，B辑卷。37，没有。3，第221-227，1984。查看在：出版商网站|谷歌学术|MathSciNet
4. R、 古尔德，“哈密顿问题的进展——综述”图表和组合卷。19，没有。1，第7-52，2003。查看在：出版商网站|谷歌学术|MathSciNet
5. Vandergriend，罗勒（1998年），查找哈密顿圈：算法，图形和性能[硕士论文]，研究生学习和研究，阿尔伯塔大学，1998年学院。
6. F.鲁宾，“汉密尔顿路径和电路A搜索过程，”ACM杂志卷。21，第576-580，1974。查看在：出版商网站|谷歌学术|MathSciNet
7. N.赫里斯托菲，图论:一种算法方法，计算机科学和应用数学，学术出版社，纽约，纽约，美国，1975年。查看在：MathSciNet
8. W. Kocay，“用于发现汉密尔顿周期多路径算法的扩展，”离散数学卷。101，没有。1-3，第171-188，1992。查看在：出版商网站|谷歌学术|MathSciNet
9. S.的Martello，“算法595：的枚举法有向图中查找哈密顿电路”ACM交易在数学软件卷。9，没有。1，第131-138，1983。查看在：出版商网站|谷歌学术
10. V. Ejov，J.A.丝状体，S. K.卢卡斯，和J. L.纳尔逊，“使用符号决定解决Hamilton回路问题，”台湾数学杂志卷。10，没有。2，第327-338，2006年。查看在：出版商网站|谷歌学术
11. L. POSA，“在随机图哈密顿电路”离散数学卷。14，没有。4，第359-364页，1976年。查看在：出版商网站|谷歌学术|MathSciNet
12. D. Angluin和L. G.勇士“哈密尔顿电路与对集快速概率算法，”在第九届计算理论学术年会论文集， 30-41页，ACM, 1977。查看在：谷歌学术
13. B.Bollobás，T. I.芬纳和A. M.楣，“用于发现在随机图汉密尔顿路径和循环的算法，”组合学，概率论与数计算，第7卷第1期4，第327-341页，1987。查看在：出版商网站|谷歌学术
14. A. M.楣，“用于发现在随机向图汉密尔顿圈的一个算法，”算法杂志卷。9，没有。2，第181-204，1988。查看在：出版商网站|谷歌学术|MathSciNet
15. A. Z.布罗德，A. M.楣和E.沙米尔，“寻找隐藏Hamilton圈，”随机结构和算法卷。5，没有。3，第395-410，1994。查看在：出版商网站|谷歌学术
16. F. A. Brunacci，“DB2和DB2A：构建哈密顿电路两个有用的工具，”欧洲运筹学杂志卷。34，没有。2，第231-236，1988。查看在：出版商网站|谷歌学术|MathSciNet
17. S. Lin和B. W. Kernighan的，“一个有效的启发式算法进行巡回推销员问题”运筹学，第21卷，第498-5161973页。查看在：出版商网站|谷歌学术|MathSciNet
18. K. Helsgaun，“有效地实施林Kernighan的旅行商启发式”欧洲运筹学杂志卷。126，没有。1，第106-130，2000。查看在：出版商网站|谷歌学术|MathSciNet
19. S.林，“旅行商问题的计算机解决方案，”贝尔实验室技术杂志，第44卷，第2245-2269页，1965。查看在：出版商网站|谷歌学术|MathSciNet
20. M. M.洪水“则行推销员问题”运筹学，第4卷，第61-75页，1956年。查看在：出版商网站|谷歌学术|MathSciNet
21. P. Baniasadi，V. Ejov，J.A.丝状体，M. Haythorpe和S. Rossomakhine，“确定性‘蛇和梯子’启发式的哈密顿周期的问题，”数学编程计算，第6卷，第1期，第55-75页，2014年。查看在：出版商网站|谷歌学术
22. TSPLIB-Hamiltonian cycle problem (HCP)， 2013年6月访问，http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95。
23. PCGRATE，在2014年9月访问http://www.pcgrate.com/about/npcomprb/hcp。
24. 协和广场，在2014年9月访问http://www3.cs.stonybrook.edu/~algorith/implement/concorde/implement.shtml。
25. M. Haythorpe，“FHCP挑战组：第一组汉密尔顿的周期问题，结构上难以实例，”组合数学研究所及其应用的公告卷。83，第98-107，2018。查看在：谷歌学术|MathSciNet
26. 施耐德:“当研究人员试图解决1001个哈密顿循环问题时，”2016年，https://www.inria.fr/en/centre/sophia/news/when-researches-play-to-solve-1001-instances-of-the-hamiltonian-cycle-problem。查看在：谷歌学术

版权

版权所有©2018 K. R. Seeja。这是下发布的开放式访问文章知识共享署名许可，其允许在任何介质无限制地使用，分发和再现时，所提供的原始工作正确的引用。