回溯搜索方法和路径扩展方法是判定无向哈密顿图的两种重要途径,其缺点是要么进行路径选择的回溯,从而造成指数阶时间开销,要么由于剪枝技术而遗漏正确答案.任何一个无向哈密顿圈总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通.根据这个特征,文中使用原子圈和基本圈作为染色体,设计成可拼接/可分解的遗传编码,提出一种新的自适应遗传算法,用于降低时间开销,保证正确判定.对一些实际案例的测试结果验证了该算法的有效性.

The two important methods of distinguishing undirected Hamiltonian graphs,namely the backtracking search and the path extension,are both of their own disadvantages.Specifically,the former requires some backtracking operations on path selection,which results in exponential time cost.However,the latter may fail in finding correct answers due to the branch trimming.As any undirected Hamiltonian cycle can always be decomposed into several atomic cycles which are connected with one another by one common edge in a certain order,atomic cycles and basic cycles are used as chromosomes to derive a genetic code with the properties of splicing and decomposing,and a new adaptive genetic algorithm based on the genetic code is proposed to reduce the time cost and guarantee the distinguishing.Experimental results on some real cases demonstrate that the proposed algorithm is effective.