CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

Prosser's hybrid algorithms for the Constraint Satisfaction Problem

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.

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