尋找哈密爾頓回路的一種高效算法

打開(kāi)文本圖片集

摘要：針對(duì)基于深度優(yōu)先搜索的尋找哈密爾頓回路算法，首次采用必選邊和分層檢測(cè)機(jī)制對(duì)解空間的搜索樹(shù)進(jìn)行大量裁剪，從而使得算法能夠處理絕大部分含幾百個(gè)頂點(diǎn)的無(wú)向圖。

關(guān)鍵詞：哈密爾頓回路；必選邊；分層檢測(cè)；深度優(yōu)先搜索

doi：10.3969/J.ISSN.1672-7274.2023.03.029

中圖分類號(hào)：TP 302               文獻(xiàn)標(biāo)示碼：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

設(shè)G=（V，E）是有n個(gè)頂點(diǎn)e條邊的連通無(wú)向圖，，，如果頂點(diǎn)序列x1x2…xn的各個(gè)頂點(diǎn)互不相同，并且對(duì)于i=1，2，…n-1，（xi，xi+1）∈E，以及（x1，xn）∈E，則稱該序列是G的一條哈密爾頓回路。（剩余3316字）