Pruning Techniques to Reduce Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Search Tree without Pruning:
=====================================
                    Root
                   /    \
                  A      B
                 /|\    /|\
                1 2 3  4 5 6
               ... ... ... ...
               
All branches explored, even doomed ones.
Total nodes visited: Thousands to billions
 
Search Tree WITH Pruning:
=====================================
                    Root
                   /    \
                  A      B (pruned - constraint violation detected)
                 /|\      ╳
                1 2 3
               /  |  \
              ...  ╳  ╳   (pruned - domains would become empty)
              
Only viable branches explored.
Total nodes visited: Often orders of magnitude fewer
 
The power of pruning: Not avoiding slow paths,
but avoiding MOST paths entirely.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Basic feasibility pruning: check constraints after assignment
function isFeasible<T>(
  assignment: Map<string, T>,
  csp: CSP<T>,
  justAssigned: string  // The variable we just assigned
): boolean {
  // Check only constraints involving the just-assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(justAssigned)) continue;
    
    // Check if ALL variables in this constraint are now assigned
    const allAssigned = constraint.variables.every(v => assignment.has(v));
    
    if (allAssigned) {
      // Fully instantiated constraint - must be satisfied
      if (!constraint.isSatisfied(assignment)) {
        return false;  // PRUNE: This path is doomed
      }
    }
    // If not all assigned, constraint can't be checked yet
    // (This is the limitation of basic feasibility checking)
  }
  
  return true;  // No violation detected (yet)
}
 
// Backtracking with feasibility pruning
function backtrackWithFeasibility<T>(
  assignment: Map<string, T>,
  csp: CSP<T>
): Map<string, T> | null {
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  const variable = selectUnassignedVariable(assignment, csp);
  const domain = csp.domains.get(variable) || [];
  
  for (const value of domain) {
    assignment.set(variable, value);
    
    // PRUNING CHECK: Verify feasibility before recursing
    if (isFeasible(assignment, csp, variable)) {
      const result = backtrackWithFeasibility(assignment, csp);
      if (result !== null) return result;
    }
    // If not feasible, we don't recurse - that's the pruning!
    
    assignment.delete(variable);
  }
  
  return null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Domain state: tracks current domains during search
interface DomainState<T> {
  domains: Map<string, Set<T>>;  // Current valid values per variable
  
  clone(): DomainState<T>;      // For branching
  removeValue(variable: string, value: T): boolean;  // Returns true if domain became empty
  getDomain(variable: string): Set<T>;
}
 
// Basic domain reduction after an assignment
function reduceDomains<T>(
  assignment: Map<string, T>,
  domainState: DomainState<T>,
  assignedVar: string,
  assignedValue: T,
  csp: CSP<T>
): boolean {  // Returns false if any domain becomes empty (failure detection)
  
  // For each constraint involving the assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(assignedVar)) continue;
    
    // For each OTHER variable in this constraint
    for (const otherVar of constraint.variables) {
      if (otherVar === assignedVar) continue;
      if (assignment.has(otherVar)) continue;  // Already assigned
      
      // Check each value in the other variable's domain
      const otherDomain = domainState.getDomain(otherVar);
      const toRemove: T[] = [];
      
      for (const otherValue of otherDomain) {
        // Would this value be consistent with the current assignment?
        const testAssignment = new Map(assignment);
        testAssignment.set(otherVar, otherValue);
        
        if (!constraint.isSatisfied(testAssignment)) {
          // This value is INCOMPATIBLE with current assignment
          toRemove.push(otherValue);
        }
      }
      
      // Remove incompatible values
      for (const value of toRemove) {
        if (domainState.removeValue(otherVar, value)) {
          return false;  // Domain became empty! Failure detected early
        }
      }
    }
  }
  
  return true;  // No domain became empty
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

interface Bounds {
  min: number;
  max: number;
}
 
interface BoundsState {
  bounds: Map<string, Bounds>;
  
  updateMin(variable: string, newMin: number): boolean;  // Returns true if changed
  updateMax(variable: string, newMax: number): boolean;
  isEmpty(variable: string): boolean;  // min > max means empty
}
 
// Example: Propagate bounds for X + Y = sum constraint
function propagateSumConstraint(
  x: string,
  y: string, 
  sum: number,
  state: BoundsState
): boolean {  // Returns false if any bounds become invalid
  
  let changed = true;
  while (changed) {
    changed = false;
    
    const xBounds = state.bounds.get(x)!;
    const yBounds = state.bounds.get(y)!;
    
    // min[X] >= sum - max[Y]
    const newMinX = sum - yBounds.max;
    if (state.updateMin(x, newMinX)) changed = true;
    
    // max[X] <= sum - min[Y]
    const newMaxX = sum - yBounds.min;
    if (state.updateMax(x, newMaxX)) changed = true;
    
    // Similarly for Y
    const newMinY = sum - xBounds.max;
    if (state.updateMin(y, newMinY)) changed = true;
    
    const newMaxY = sum - xBounds.min;
    if (state.updateMax(y, newMaxY)) changed = true;
    
    // Check for failures
    if (state.isEmpty(x) || state.isEmpty(y)) {
      return false;  // Bounds became invalid - prune!
    }
  }
  
  return true;  // Bounds are consistent
}
 
// Example: Propagate bounds for X < Y constraint  
function propagateLessThanConstraint(
  x: string,
  y: string,
  state: BoundsState
): boolean {
  
  const xBounds = state.bounds.get(x)!;
  const yBounds = state.bounds.get(y)!;
  
  // max[X] must be less than max[Y]
  // Actually: max[X] < max[Y], but for integers: max[X] <= max[Y] - 1
  state.updateMax(x, yBounds.max - 1);
  
  // min[Y] must be greater than min[X]
  // For integers: min[Y] >= min[X] + 1
  state.updateMin(y, xBounds.min + 1);
  
  return !state.isEmpty(x) && !state.isEmpty(y);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

// Example 1: Variable Symmetry Breaking (Ordering)
// For indistinguishable variables, impose an ordering constraint
 
// In bin packing: Force items to be assigned to lower-numbered bins first
function binPackingSymmetryBreaking(
  items: number[],      // Item sizes
  binCapacity: number,
  numBins: number
): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // Each item goes to some bin (1 to numBins)
  // Symmetry breaking: item i can only use bin j if some item < i uses bin j-1
  // Simpler version: first item uses bin 1
  constraints.push({
    variables: ['item_0'],
    isSatisfied: (a) => a.get('item_0') === 1
  });
  
  // Each subsequent item uses a bin ≤ max bin used so far, or max+1
  // This prevents exploring equivalent bin permutations
  
  return constraints;
}
 
// Example 2: Value Symmetry Breaking (First-Use Ordering)
// For graph coloring: assign colors in order of first appearance
function coloringSymmetryBreaking(
  vertices: string[],
  numColors: number
): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // First vertex gets color 1
  constraints.push({
    variables: [vertices[0]],
    isSatisfied: (a) => a.get(vertices[0]) === 1
  });
  
  // Each vertex uses a color already used, or the next unused color
  // i.e., vertex i can use color c only if c <= max(colors[0..i-1]) + 1
  for (let i = 1; i < vertices.length; i++) {
    const prevVerts = vertices.slice(0, i);
    constraints.push({
      variables: [...prevVerts, vertices[i]],
      isSatisfied: (a) => {
        const myColor = a.get(vertices[i]);
        if (myColor === undefined) return true;
        
        const prevColors = prevVerts
          .map(v => a.get(v))
          .filter(c => c !== undefined) as number[];
        
        if (prevColors.length === 0) return myColor === 1;
        
        const maxPrev = Math.max(...prevColors);
        return myColor <= maxPrev + 1;
      }
    });
  }
  
  return constraints;
}
 
// Example 3: Geometric Symmetry Breaking (N-Queens)
// Remove rotational/reflectional symmetry by constraining first queen position
function nQueensSymmetryBreaking(n: number): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // Force Q1 to be in the left half of the board
  // This eliminates the horizontal reflection symmetry
  constraints.push({
    variables: ['Q1'],
    isSatisfied: (a) => {
      const col = a.get('Q1');
      if (col === undefined) return true;
      return col <= Math.ceil(n / 2);
    }
  });
  
  // Could also add: when Q1 is in middle column, force Q2 to upper half
  // This handles the remaining symmetries
  
  return constraints;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

type Nogood<T> = Map<string, T>;  // A forbidden partial assignment
 
interface NogoodStore<T> {
  nogoods: Nogood<T>[];
  
  // Add a learned nogood
  addNogood(nogood: Nogood<T>): void;
  
  // Check if current assignment contains any nogood
  containsNogood(assignment: Map<string, T>): boolean;
}
 
function createNogoodStore<T>(): NogoodStore<T> {
  const nogoods: Nogood<T>[] = [];
  
  return {
    nogoods,
    
    addNogood(nogood: Nogood<T>) {
      // Could check for subsumption: don't add if existing nogood is subset
      nogoods.push(nogood);
    },
    
    containsNogood(assignment: Map<string, T>): boolean {
      for (const nogood of nogoods) {
        // Check if all entries in nogood are present in assignment
        let matches = true;
        for (const [variable, value] of nogood) {
          if (assignment.get(variable) !== value) {
            matches = false;
            break;
          }
        }
        if (matches) return true;  // Found a matching nogood!
      }
      return false;
    }
  };
}
 
// Conflict-Directed Backjumping with Nogood Learning
function backtrackWithNogoods<T>(
  assignment: Map<string, T>,
  csp: CSP<T>,
  store: NogoodStore<T>,
  conflictVars: Set<string>[]  // Track which variables caused each constraint failure
): Map<string, T> | null {
  
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  // Check for known nogood before exploring
  if (store.containsNogood(assignment)) {
    return null;  // We've been here before and it failed
  }
  
  const variable = selectUnassignedVariable(assignment, csp);
  const domain = csp.domains.get(variable) || [];
  
  const localConflicts = new Set<string>();
  
  for (const value of domain) {
    assignment.set(variable, value);
    
    if (isConsistent(assignment, csp)) {
      const result = backtrackWithNogoods(assignment, csp, store, conflictVars);
      if (result !== null) return result;
      
      // Collect conflicts from failed subtree
      // (In full implementation, this comes from analyzing the failure)
    }
    
    assignment.delete(variable);
  }
  
  // All values failed - learn a nogood from the conflicts
  const nogood = new Map<string, T>();
  for (const conflictVar of localConflicts) {
    if (assignment.has(conflictVar)) {
      nogood.set(conflictVar, assignment.get(conflictVar)!);
    }
  }
  if (nogood.size > 0) {
    store.addNogood(nogood);
  }
  
  return null;
}