The Phase Transition in the MSP Problem
The MSP problem and its relevant polynomial-time heuristic algorithm (Z-H algorithm) proposed in ”1” provided a promising solution to a series of NP problems.Z-H algorithm has successfully passed random tests of 53,000,000 instances by far since 2010 and no error occurred.However, the current implementation of the algorithm is not capable of solving larger instances and how to better test it becomes a challenging problem.In order to better understand the problem nature and generate harder instances, we research on the phase transition of the MSP problem.Although NP-complete problems can be mapped to each other, it is no easy to determine the phase transition order parameter of the MSP problem because of its complex definition of vertex-edge sets.It is also well known that the phase transition point of different problems cannot be analytically calculated accurately via problem mapping.In this paper, we carefully determine the order parameter, and conduct computational experiments to locate the phase transition point.It has been reported previously that there are hardness transitions near the phase transition region for both backtrack and probabilistic search algorithms.In our paper, a transition for Z-H algorithm, which is neither backtrack nor probabilistic, is also observed, and thus confirms the conjecture”10” that the phase transition is intrinsic.Our model can be applied for better testing Z-H algorithm.
the MSP problem NP-completeness Z-H algorithm phase transition
Fan Shuo Wu Tian-jun Jiang Xin-wen Shao Cheng-cheng Xiao Li-quan
College of Computer Science,National University of Defense Technology,410073,Changsha,P.R.China
国内会议
金华
英文
1-10
2015-10-30（万方平台首次上网日期，不代表论文的发表时间）