[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A New Algorithm for Sampling CSP Solutions Uniformly at Random

  • Conference paper
Principles and Practice of Constraint Programming - CP 2006 (CP 2006)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 4204))

  • 1342 Accesses

Abstract

The paper presents a method for generating solutions of a constraint satisfaction problem (CSP) uniformly at random. Our method relies on expressing the constraint network as a uniform probability distribution over its solutions and then sampling from the distribution using state-of-the-art probabilistic sampling schemes. To speed up the rate at which random solutions are generated, we augment our sampling schemes with pruning techniques used successfully in constraint satisfaction search algorithms such as conflict-directed back-jumping and no-good learning.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Dechter, R.: Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition. Artificial Intelligence 41, 273–312 (1990)

    Article  MathSciNet  Google Scholar 

  2. Dechter, R., Kask, K., Bin, E., Emek, R.: Generating random solutions for constraint satisfaction problems. In: AAAI (2002)

    Google Scholar 

  3. Dechter, R., Kask, K., Mateescu, R.: Iterative join graph propagation. In: UAI 2002, pp. 128–136. Morgan Kaufmann, San Francisco (2002)

    Google Scholar 

  4. Gogate, V., Dechter, R.: Approximate inference algorithms for hybrid bayesian networks with discrete constraints. In: UAI 2005 (2005)

    Google Scholar 

  5. Gogate, V., Dechter, R.: A new algorithm for sampling csp solutions uniformly at random. Technical report, University of California, Irvine (2006)

    Google Scholar 

  6. Wei, W., Erenrich, J., Selman, B.: Towards efficient sampling: Exploiting random walk strategies. In: AAAI (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Donald Bren School of Information and Computer Science, University of California, Irvine, CA, 92697

    Vibhav Gogate & Rina Dechter

Authors
  1. Vibhav Gogate
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rina Dechter
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LINA UMR CNRS 6241, University of Nantes,  

    Frédéric Benhamou

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gogate, V., Dechter, R. (2006). A New Algorithm for Sampling CSP Solutions Uniformly at Random. In: Benhamou, F. (eds) Principles and Practice of Constraint Programming - CP 2006. CP 2006. Lecture Notes in Computer Science, vol 4204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11889205_56

Download citation

  • DOI: https://doi.org/10.1007/11889205_56

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-46267-5

  • Online ISBN: 978-3-540-46268-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics