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