科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
