Published:
May 2001
Proceedings:
Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)
Volume
Issue:
Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)
Track:
All Papers
Downloads:
Abstract:
Decision and optimization problems involving graphs arise in many areas of artificial intelligence, including probabilistic networks, robot navigation, and network design. Many such problems are NP-complete; this has necessitated the development of approximation methods, most of which are very complex and highly problemspecific. We propose a straightforward, practical approach to algorithm design based on Markov Chain Monte Carlo (MCMC), a statistical simulation scheme for efficiently sampling from a large (possibly exponential) set, such as the set of feasible solutions to a combinatorial task. This facilitates the development of simple, efficient, and general solutions to whole classes of decision problems. We provide detailed examples showing how this approach can be used for spanning tree problems such as Degree-Constrained Spanning Tree, Maximum Leaf Spanning Tree, and Kth Best Spanning Tree.
FLAIRS
Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)
ISBN 978-1-57735-133-7
Published by The AAAI Press, Menlo Park, California.