智能系统学报
智能繫統學報
지능계통학보
CAAI TRANSACTIONS ON INTELLIGENT SYSTEMS
2012年
6期
506-511
,共6页
谷文祥%傅琳璐%周俊萍%姜蕴晖
穀文祥%傅琳璐%週俊萍%薑蘊暉
곡문상%부림로%주준평%강온휘
NAESAT%NAE-3SAT%时间复杂性%NAE-3SAT问题上界%变量数目%分支回溯
NAESAT%NAE-3SAT%時間複雜性%NAE-3SAT問題上界%變量數目%分支迴溯
NAESAT%NAE-3SAT%시간복잡성%NAE-3SAT문제상계%변량수목%분지회소
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.
NAESAT問題是可滿足性問題的一箇重要擴展,在集閤分裂、最大割集等NP完全問題中有著重要的應用.針對NAESAT問題的汎化NAE-3SAT問題,提齣瞭一箇基于分支迴溯的精確算法NAE.算法給齣瞭多種化簡規則,這些化簡規則很好地提高瞭算法的時間效率.最後證明瞭算法在最壞情況下的時間複雜度上界為O(1.618n),其中n為公式中的變量數目.
NAESAT문제시가만족성문제적일개중요확전,재집합분렬、최대할집등NP완전문제중유착중요적응용.침대NAESAT문제적범화NAE-3SAT문제,제출료일개기우분지회소적정학산법NAE.산법급출료다충화간규칙,저사화간규칙흔호지제고료산법적시간효솔.최후증명료산법재최배정황하적시간복잡도상계위O(1.618n),기중n위공식중적변량수목.
