寻找哈密尔顿回路的一种高效算法

打开文本图片集

摘要：针对基于深度优先搜索的寻找哈密尔顿回路算法，首次采用必选边和分层检测机制对解空间的搜索树进行大量裁剪，从而使得算法能够处理绝大部分含几百个顶点的无向图。

关键词：哈密尔顿回路；必选边；分层检测；深度优先搜索

doi：10.3969/J.ISSN.1672-7274.2023.03.029

中图分类号：TP 302               文献标示码：A               文章编码：1672-7274（2023）03-00-03

An Efficient Algorithm for Finding Hamiltonian Circuits

HAN Hai

（School of Artificial Intelligence， Jianghan University， Wuhan 430056， China）

Abstract： For the first time， the required edge and hierarchical detection mechanism are used to cut a large number of search trees in the solution space， so that the algorithm can deal with most undirected graphs containing hundreds of vertices.

Key words： hamilton circuit; required edges; layered detection; depth-first search

设G=（V，E）是有n个顶点e条边的连通无向图，，，如果顶点序列x1x2…xn的各个顶点互不相同，并且对于i=1，2，…n-1，（xi，xi+1）∈E，以及（x1，xn）∈E，则称该序列是G的一条哈密尔顿回路。（剩余3316字）