NetLogo banner

 Home
 Download
 Help
 Resources
 Extensions
 FAQ
 References
 Contact Us
 Donate

 Models:
 Library
 Community
 Modeling Commons

 User Manuals:
 Web
 Printable
 Chinese
 Czech
 Japanese

  Donate

NetLogo User Community Models

(back to the NetLogo User Community Models)

Asynchronous_Backtracking_-_binary_random_problems

by Ionel Muscalagiu (Submitted: 03/06/2006)

[screen shot]

Download Asynchronous_Backtracking_-_binary_random_problems
If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses external files.)

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 Multi-Agent Systems,</i> 3(2):185--207, 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 4-tuple (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).

(back to the NetLogo User Community Models)