Stochastic search and phase transitions: AI meets physics
作者： Bart Selman
DOI:
关键词: Phenomenon 、 Physics 、 Phase transition 、 Artificial intelligence 、 Critical ratio 、 Statistical physics
摘要: Computationally hard instances of combinatorial problems arise at a certain critical ratio constraints to variables. At the ratio, problem distributions undergo dramatic changes. I will discuss how an analogous phenomenon occurs in phase transitions studied physics, and experiments with critically constrained have led surprising new insights into average-case complexity stochastic search methods AI.
ijcai.org
acm.org 参考文章(61)
Andrew B. Philips, Steven Minton, Philip Laird, Mark D. Johnston, Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method national conference on artificial intelligence. pp. 17- 24 ,(1990)
Bart Selman, David Mitchell, Hector Levesque, Hard and easy distributions of SAT problems national conference on artificial intelligence. pp. 459- 465 ,(1992)
Paul Morris, The breakout method for escaping from local minima national conference on artificial intelligence. pp. 40- 45 ,(1993)
Bart Selman, Henry A. Kautz, An empirical study of greedy local search for satisfiability testing national conference on artificial intelligence. pp. 46- 51 ,(1993)
Bart Selman, Henry Kautz, Hard problems for simple default theories Artificial Intelligence. ,(1991)
Edward Tsang, Chang J. Wang, Kangmin Zhu, Andrew Davenport, GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement national conference on artificial intelligence. pp. 325- 330 ,(1994)
Holger H. Hoos, Antje Beeringer, Michael Metzger, Andreas Weiss, Gerd Aschemann, GSAT versus simulated annealing european conference on artificial intelligence. pp. 130- 134 ,(1994)
Bart Selman, Henry Kautz, Domain-independent extensions to GSAT: solving large structured satisfiability problems international joint conference on artificial intelligence. pp. 290- 295 ,(1993)
Tad Hogg, Colin P. Williams, Expected gains from parallelizing constraint solving for hard problems national conference on artificial intelligence. pp. 331- 336 ,(1994)
Bart Selman, Henry Kautz, Yuejun Jiang, Solving Problems with Hard and Soft Constraints Using a Stochastic Algorithm for MAX-SAT ,(1995)