一种求解哈密尔顿通路问题的新方法  

Novel method to solve Hamilton loop problem

作　　者：孟祥萍[1] 孟军[2] 吕利娟[3] 

机构地区：[1]长春工程学院电气与信息学院,长春130012 [2]长春工业大学计算机科学与工程学院,长春130012 [3]长春工业大学电气与电子工程学院,长春130012

出　　处：《计算机应用研究》2008年第12期3561-3562,3577,共3页Application Research of Computers

基　　金：国家教育部科学与技术研究资助项目(206035);吉林省科技厅资助项目(20070530)

摘　　要：哈密尔顿通路问题属于典型的NP完全问题。针对NP完全问题的特点提出了一种基于量子计算和混沌动力学的新方法。该方法首先把哈密尔顿问题变换成布尔表达式形式;然后构建了一个新型的量子混沌计算机模型,该模型使用混沌放大器解决了量子状态区分问题;最后得出结论,基于非线性迭代关系的新型量子混沌计算机可以在多项式时间内解决哈密尔顿通路问题。Hamilton loop problem belongs to NP-complete problems. This paper proposed an approach to it based on quantum computation and chaotic dynamics. Firstly, using a Boolean polynomial analyzed the Hamilton loop problem. Secondly, constructed a novel model based on quantum computation and chaotic dynamics which using a chaotic dynamics amplifier amplified the initial value in polynomial time. Considered the Hamilton loop problem and argued that the problem, in principle, it could be solved in polynomial time if the quantum computer was combined with the chaotic dynamics amplifier based on the logistic

关 键 词：哈密尔顿通路 量子计算 混沌动力学 放大器 非线性迭代关系 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]