NP完全问题多项式时间算法研究  

Study on the Polynomial-time Algorithms of NP Complete Problems

作　　者：石海林 

机构地区：[1]马鞍山矿山研究院信息中心,安徽243004

出　　处：《应用数学》2001年第S1期107-112,共6页Mathematica Applicata

基　　金：国家重点研究院试点扶持资金资助

摘　　要：本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .In this paper, the polynimial time algorithms of the NP complete problems are gained in the algebraical and combinatorial two aspects respectively. Since there were subtours, the linear programming (LP) technics was inefficient in the past, which was used to analysed the travelling salesman problem (TSP). A layer network is developed in the paper, there are another type (uncomplete) subtours. However, the intersect set of the feasible solution sets of the two models don't contain the two subtours basic feas...

关 键 词：NP完全问题 LP技术 多项式时间算法 哈密尔顿回路 TSP问题 群 

分 类 号：O157.5[理学—数学]