CMU Artificial Intelligence Repository
Prosser's hybrid algorithms for the Constraint Satisfaction
Problem
lang/lisp/code/csp/
This directory contains Patrick Prosser's hybrid algorithms for the
binary constraint satisfaction problem. Search algorithms include
chronological backtracking, backmarking, backjumping, forward
checking, graph-based backjumping, conflict-directed backjumping,
backjumping with directed 2-consistency, forward checking with
directed 2-consistency, conflict directed backjumping with directed
k-consistency, forward checking with conflict-directed backjumping,
with directed k-consistency, and various combinations.
Origin:
ftp.daimi.aau.dk:pub/CLP/Prosserpackage.tar.Z
Ports: SCLisp 4.0 (developed using the Symbolic Programming
Environment, SPE 1.2)
CD-ROM: Prime Time Freeware for AI, Issue 1-1
Author(s): Patrick Prosser
Keywords:
Authors!Prosser, Backjumping, Backmarking, Backtracking, CSP,
Constraint Satisfaction, Forward Checking, Lisp!Code
References:
The algorithms are described in the following papers:
[1] P. Prosser "Hybrid algorithms for the constraint satisfaction
problem", to appear in Computational Intelligence 9(3),
Autumn 1993 (previously technical report AISL-46-91)
[2] P. Prosser "BM+BJ=BMJ" Proc CAIA-93, 257-262
[3] P. Prosser "Domain filtering can degrade intelligent
backjumping search" to appear in Proc IJCAI-93
[4] P. Prosser "Forward checking with backmarking" Technical
Report AISL-48-93, Dept CS, Univ Strathclyde, Scotland
Last Web update on Mon Feb 13 10:29:20 1995
AI.Repository@cs.cmu.edu