Home
Download
Help
Resources
Extensions
FAQ
References
Contact Us
Donate
Models:
Library
Community
Modeling Commons
User Manuals:
Web
Printable
Chinese
Czech
Japanese

NetLogo User Community Models(back to the NetLogo User Community Models)
Asynchronous_Backtracking__binary_random_problems
by Ionel Muscalagiu
(Submitted: 03/06/2006)
Title: Random binary CSPs using Asynchronous Backtracking Author: Ionel Muscalagiu, Jose M. Vidal and Hong Jiang Description: This is the implementation of the Asynchronous Backtracking for the random binary problems. We generate and solve the random binary problem using the Asynchronous Backtracking algorithm from <ul> <li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/library/yokoo00a.pdf">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and MultiAgent Systems,</i> 3(2):185207, 2000. <a href="http://dx.doi.org/10.1023/A:1010078712316">doi:10.1023/A:1010078712316</a> </li> </ul> The randomly generated (binary) CSPs are characterised by the 4tuple (n, m,p1,p2), where n is the number of variables, m is the uniform domain size, p1 is the portion of the n * (n  1) /2 possible constraints in the graph, and p2 is the portion of the m*m value pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.
In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n  1)/2 constraints are randomly selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
