Iterative algorithms for CSPs Summary ced set of variable ogBCPneidcoesnt Backtracking=depth-first search with one variable assigned per node operators reassign variable values Variable ordering and value selection heuristics help significantly Variable selection:randomly select any conflicted variable Forward checking prevents assignments that guarantee later failure 的c The CSP representation allows analysis of problem structure Tree-structured CSPs can be solved in linear time Iterative min-conflicts is usually effective in practice Example:4-Queens States:4 queens in 4 columns (=256 states) Operators:move queen in column Goal test:no attacks Evaluation:(n)=number of attacks Performance of min-conflicts in amost constant time for The same appears to be true for any randomly-generated CSP except in a narrow range of the ratio R=number of constraints umber of variables d Iterative algorithms for CSPs Hill-climbing, simulated annealing typically work with “complete” states, i.e., all variables assigned To apply to CSPs: allow states with unsatisfied constraints operators reassign variable values Variable selection: randomly select any conflicted variable Value selection by min-conflicts heuristic: choose value that violates the fewest constraints i.e., hillclimb with h(n) = total number of violated constraints Chapter 5 37 Example: 4-Queens States: 4 queens in 4 columns (4 4 = 256 states) Operators: move queen in column Goal test: no attacks Evaluation: h(n) = number of attacks h = 5 h = 2 h = 0 Chapter 5 38 Performance of min-conflicts Given random initial state, can solve n-queens in almost constant time for arbitrary n with high probability (e.g., n = 10,000,000) The same appears to be true for any randomly-generated CSP except in a narrow range of the ratio R = number of constraints number of variables R CPU time critical ratio Chapter 5 39 Summary CSPs are a special kind of problem: states defined by values of a fixed set of variables goal test defined by constraints on variable values Backtracking = depth-first search with one variable assigned per node Variable ordering and value selection heuristics help significantly Forward checking prevents assignments that guarantee later failure Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies The CSP representation allows analysis of problem structure Tree-structured CSPs can be solved in linear time Iterative min-conflicts is usually effective in practice Chapter 5 40