摘要: The traveling salesman problem is one of the most famous combinatorial problems. We identify a natural parameter for two-dimensional Euclidean problem. show that random problems there rapid transition between soluble and insoluble instances decision at critical value this parameter. Hard are associated with transition. Similar results seen both randomly generated benchmark using geographical data. Surprisingly, finite-size scaling methods developed in statistical mechanics describe behaviour around Such phase phenomena appear to be ubiquitous. Indeed, we have yet find an NP-complete which lacks similar
elsevier.com
unsw.edu.au 
sci-hub.se 参考文章(24)
Bart Selman, David Mitchell, Hector Levesque, Hard and easy distributions of SAT problems national conference on artificial intelligence. pp. 459- 465 ,(1992)
Barbara M. Smith, The phase transition and the mushy region in constraint satisfaction problems european conference on artificial intelligence. pp. 100- 104 ,(1994)
Patrick Prosser, Binary Constraint Satisfaction Problems: Some are Harder than Others. european conference on artificial intelligence. pp. 95- 99 ,(1994)
Richard E. Korf, Weixiong Zhang, An average-case analysis of branch-and-bound with applications: summary of results national conference on artificial intelligence. pp. 545- 550 ,(1992)
David Shmoys, Eugene L. Lawler, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, The traveling salesman problem ,(1985)
John L. Cardy, Finite-size scaling North-Holland , Sole distributors for the USA and Canada, Elsevier Science Pub. Co.. ,(1988)
Ian P. Gent, Toby Walsh, The Hardest Random SAT Problems KI '94 Proceedings of the 18th Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence. pp. 355- 366 ,(1994) , 10.1007/3-540-58467-6_31
Bob Kanefsky, Peter Cheeseman, William M. Taylor, Where the really hard problems are international joint conference on artificial intelligence. pp. 331- 337 ,(1991)
Ian P. Gent, Ewan MacIntyre, Patrick Prosser, Toby Walsh, Scaling Effects in the CSP Phase Transition principles and practice of constraint programming. pp. 70- 87 ,(1995) , 10.1007/3-540-60299-2_5
S. Kirkpatrick, B. Selman, Critical Behavior in the Satisfiability of Random Boolean Expressions Science. ,vol. 264, pp. 1297- 1301 ,(1994) , 10.1126/SCIENCE.264.5163.1297