chap 5 in AIMI - Constraint problems.
--- ensign problem ----------------
Assign N ensigns to N-1 tasks in a
calendar grido of N-1 weeks.
For N=6, a partial grid looks like this.
1 2 3 4 5 6 = ensign
-------------
1 | 1 1 2 2 3 3
2 | 2 3 2
3 | 3 4 3
4 | 4 5 4
5 | 5 2 5
week
The constraints are:
1. Each column is a permutation of 1 .. 5,
so that each ensign does each task once.
2. Each row consists of 4 pairs, i.e. 1 1 2 2 3 3 4 4,
so that they learn to work with each other.
3. Each ensign is pairs with every other exactly once.
- - - - - - - - - - - - - - -
concepts from the text:
Problem :
Assign VARIABLES { Xi } to
values in DOMAIN of possibilities (v1,v2,...)
subject to CONSTRAINT conditions C1, C2, ...
STATE of system is { X1=v1, X2=v2, ... }
The GOAL is a state that satisfies all the conditions.
For finite problems one can always choose extra variables
and a domain such that the constraints are all
binary ones involving only pairs of variables, which
can help in coding a general algorithm.
There are two broad approaches.
(I) Depth first, partial (correct) assignment.
* Backtracking search
* Choose next node to expand by one with MINMUM REMAINING VALUES
* After assignment, propogate constraints by FORWARD CHECKING
to illegal values from the domains of other variables.
* May also perform CONSTRAINT CHECKING on pairs of
variables to see there exist consistent assignments
before moving forward with full search
* May use a CONFLICT SET which includes all previously assigned
variables which constrain this one to determine
how far to backtrack. These conflict sets are propogated
backwards as well.
(II) Local search, complete (though incorrect) assignment.
* greedy - move towards states with fewer conflicts.
* particularly effective if many solutions