无向哈密顿图的自适应遗传算法 (2011年)

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