南京理工大学学报（自然科学版）
南京理工大學學報（自然科學版）
남경리공대학학보（자연과학판）
JOURNAL OF NANJING UNIVERSITY OF SCIENCE AND TECHNOLOGY
2013年
4期
506-510
,共5页
计算机算法%哈密尔顿环%三元可满足性问题%非确定性多项式时间完全
計算機算法%哈密爾頓環%三元可滿足性問題%非確定性多項式時間完全
계산궤산법%합밀이돈배%삼원가만족성문제%비학정성다항식시간완전
computer algorithm%Hamilton cycle%3-satisfiability problem%nondeterministic polynomial time complete
为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究.通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化.研究结果表明:该转化所需要的节点数及其边数是最优的.
為瞭得到將三元可滿足性問題(3-Satisfiability problem,3SAT)直接轉化為哈密爾頓環(Hamilton cycle)的高效轉化方法,該文以長年對哈密爾頓環研究計算所探索齣的規律為基礎進行研究.通過對各種可能實現轉化的圖形組閤進行全麵的比較分析,得齣用無嚮圖的兩箇節點模擬3SAT的一箇變量,用無嚮圖的13箇節點模擬3SAT的一箇子式的方法,實現瞭3SAT到哈密爾頓環的高效轉化.研究結果錶明:該轉化所需要的節點數及其邊數是最優的.
위료득도장삼원가만족성문제(3-Satisfiability problem,3SAT)직접전화위합밀이돈배(Hamilton cycle)적고효전화방법,해문이장년대합밀이돈배연구계산소탐색출적규률위기출진행연구.통과대각충가능실현전화적도형조합진행전면적비교분석,득출용무향도적량개절점모의3SAT적일개변량,용무향도적13개절점모의3SAT적일개자식적방법,실현료3SAT도합밀이돈배적고효전화.연구결과표명:해전화소수요적절점수급기변수시최우적.
