142 Chapter 5.Constraint Satisfaction Problems function RECURSIVE-BACKTRACKING(assignment,csp)returns a solution,or failure if assignment is complete then return assignment rEC-UMASIONED-VARABLEVARALEnp) arue in ORDE result-RECURSIVE-BACKTRACKING(assignment,csp) SELECT-UNASSIGNEDVARLRE MAIN-VALUESD ment the general-purpose heuristics discussed in the text. WAgroen wehtscxamcgocadanhtatgwpo incremental successor generation described on page 76.Also,it extends the current assign ment to generate a successor,rather than copying it.Because the representation of CSPs is standardized,there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state,successor function,or goal test.Part of the search tree for the Australia problem is shown in Figure 5.4.where we have assigned variables in the order WA.NT.O. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3,so we do not expect it to be very effective for large problems.The results for some sample problems nCegemeR5omeoeasehennsh are showr
142 Chapter 5. Constraint Satisfaction Problems function BACKTRACKING-SEARCH(csp) returns a solution, or failure return RECURSIVE-BACKTRACKING({ }, csp) function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure if assignment is complete then return assignment var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp) for each value in ORDER-DOMAIN-VALUES(var , assignment, csp) do if value is consistent with assignment according to CONSTRAINTS[csp] then add {var = value} to assignment result ← RECURSIVE-BACKTRACKING(assignment, csp) if result 6= failure then return result remove {var = value} from assignment return failure Figure 5.3 A simple backtracking algorithm for constraint satisfaction problems. The algorithm is modeled on the recursive depth-first search of Chapter 3. The functions SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES can be used to implement the general-purpose heuristics discussed in the text. WA=red WA=green WA=blue WA=red NT=blue WA=red NT=green WA=red NT=green Q=red WA=red NT=green Q=blue Figure 5.4 Part of the search tree generated by simple backtracking for the map-coloring problem in Figure 5.1. incremental successor generation described on page 76. Also, it extends the current assignment to generate a successor, rather than copying it. Because the representation of CSPs is standardized, there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state, successor function, or goal test. Part of the search tree for the Australia problem is shown in Figure 5.4, where we have assigned variables in the order WA, NT, Q, . . .. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3, so we do not expect it to be very effective for large problems. The results for some sample problems are shown in the first column of Figure 5.5 and confirm our expectations. In Chapter 4 we remedied the poor performance of uninformed search algorithms by supplying them with domain-specific heuristic functions derived from our knowledge of the problem. It turns out that we can solve CSPs efficiently without such domain-specific knowl-
Section 5.2. Backtracking Search for CSPs 143 Problem Backtracking BT+MRV Forward Checking FC+MRY Min-Conflicts (000 6 817 415 Random 2 942K 27K 77K 15K Figure 5.5 o right re simple orwa cell is the median number of consistenc checks (over five runs)required to solve the p lem;note that all entries except the two in the upper right are in thousands(K).Numbers in parentheses mean that no answer was found in the allotted number of checks.The first prob em is finding a ne 3 /1005 the total number of checks required to solve all n-Que problems for from 2 to 50 The third is the"Zebra Puzzle,"as described in Exercise 5.13.The last two are artificial random was not run on thes han the rward checking ot alwa edge.Instead,we find general-purpose methods that address the following questions: 1.Which variable should be assigned next,and in what order should its values be tried? 2.What are the implications of the current variable assignments for the other unassigned variables? 3.When a path fails-that is,a state is reached in which a variable has no legal values- can the search avoid repeating this failure in subsequent paths? The subsections that follow answer each of these questions in turn. Variable and value ordering The backtracking algorithm contains the line var+-SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp). By default,SELECT-UNASSIGNED-VARIABLE simply selects the next unassigned variable in the order given by the list VARIABLES[csp].This static variable ordering seldom results in the most efficient search.For example,after the assignments for WA=red and NT=green, there is only one possible value for SA,so it makes sense to assign SA=blue next rather than assigning Q.In fact,after SA is assigned,the choices for Q,NSW,and V are all forced.This intuitive idea-choosing the variable with the fewest"legal"values-is called the minimum remaining values(MRV)heuristic.It also has been called the"most constrained variable"or "fail-first"heuristic,the latter because it picks a variable that is most likely to cause a failure soon,thereby pruning the search tree.If there is a variable X with zero legal values remain- ing.the MRV heuristic will select X and failure will be detected immediately-avoiding pointless searches through other variables which always will fail when X is finally selected
Section 5.2. Backtracking Search for CSPs 143 Problem Backtracking BT+MRV Forward Checking FC+MRV Min-Conflicts USA (> 1,000K) (> 1,000K) 2K 60 64 n-Queens (> 40,000K) 13,500K (> 40,000K) 817K 4K Zebra 3,859K 1K 35K 0.5K 2K Random 1 415K 3K 26K 2K Random 2 942K 27K 77K 15K Figure 5.5 Comparison of various CSP algorithms on various problems. The algorithms from left to right, are simple backtracking, backtracking with the MRV heuristic, forward checking, forward checking with MRV, and minimum conflicts local search. Listed in each cell is the median number of consistency checks (over five runs) required to solve the problem; note that all entries except the two in the upper right are in thousands (K). Numbers in parentheses mean that no answer was found in the allotted number of checks. The first problem is finding a 4-coloring for the 50 states of the United States of America. The remaining problems are taken from Bacchus and van Run (1995), Table 1. The second problem counts the total number of checks required to solve all n-Queens problems for n from 2 to 50. The third is the “Zebra Puzzle,” as described in Exercise 5.13. The last two are artificial random problems. (Min-conflicts was not run on these.) The results suggest that forward checking with the MRV heuristic is better on all these problems than the other backtracking algorithms, but not always better than min-conflicts local search. edge. Instead, we find general-purpose methods that address the following questions: 1. Which variable should be assigned next, and in what order should its values be tried? 2. What are the implications of the current variable assignments for the other unassigned variables? 3. When a path fails—that is, a state is reached in which a variable has no legal values— can the search avoid repeating this failure in subsequent paths? The subsections that follow answer each of these questions in turn. Variable and value ordering The backtracking algorithm contains the line var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp). By default, SELECT-UNASSIGNED-VARIABLE simply selects the next unassigned variable in the order given by the list VARIABLES[csp]. This static variable ordering seldom results in the most efficient search. For example, after the assignments for WA = red and NT = green, there is only one possible value for SA, so it makes sense to assign SA = blue next rather than assigning Q. In fact, after SA is assigned, the choices for Q, NSW , and V are all forced. This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum remaining values (MRV) heuristic. It also has been called the “most constrained variable” or MINIMUM REMAINING VALUES “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If there is a variable X with zero legal values remaining, the MRV heuristic will select X and failure will be detected immediately—avoiding pointless searches through other variables which always will fail when X is finally selected
144 Chapter 5.Constraint Satisfaction Problems .labeled BT+MRV.shws mance of this heuristic 000 times depending on the prob that our pe compu a n that ma manage help at all in choosing the firs gion to co or in Australi initially every region has three ors. In this case degree heuristic comes choices by selecting the var able that is involved in the largest number of constraints on other unassigned variables.In Figure 5.1,SA is the variable with highest degree,5:the other variables have degree 2 or except for T,which has 0.In fact,once SA is chosen,applying the degree heuristic solves the problem without any false steps-you can choose any consistent color at each choice point and still arrive at a solution with no backtracking.The minimum remaining valucs heuristic is usually a more powerful guide,but the degree heuristic can be useful as a tie-breaker. Once a variable has been selected,the algorithm must decide on the order in which to 器uwe examine its values.For this,the least-constraining-value heuristic can be effective in some cases.It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.For example,suppose that in Figure 5.1 we have generated the partial assignment with WA=red and NT=green,and that our next choice is for Q.Blue would be a bad choice,because it eliminates the last legal value left for O's neighbor,SA.The least-constraining-value heuristic therefore prefers red to blue.In general,the heuristic is trying to leave the maximum flexibility for subsequent variable assignments.Of course,if we are trying to find all the solutions to a problem,not just the first one,then the ordering does not matter because we have to consider every value anyway.The same holds if there are no solutions to the problem. Propagating information through constraints So far our search algorithm considers the constraints on a variable only at the time that the variable is chosen by SELECT-UNASSIGNED-VARIABLE.But by looking at some of the constraints earlier in the search,or even before the search has started,we can drastically reduce the search space. Forward checking CHECANS One way to make better use of constraints during search is called forward checking.When ever a variable X is assigned,the forward checking process looks at each unassigned variable Y that is connected to x by a constraint and deletes from y's domain any value that is in- consistent with the valuc chosen for X.Figure 5.6 shows the progress of a map-coloring search with forward checking.There are two important points to notice about this exam. ple.First,notice that after assigning WA=red and Q=green,the domains of NT and SA are reduced to a single value:we have eliminated branching on these variables altogether by propagating information from WA and Q.The MRV heuristic.which is an obvious part. ner for forward checking.would automatically select SA and NT next.(Indeed,we can view forward checking as an efficient way to incrementally compute the information that the
144 Chapter 5. Constraint Satisfaction Problems The second column of Figure 5.5, labeled BT+MRV, shows the performance of this heuristic. The performance is 3 to 3,000 times better than simple backtracking, depending on the problem. Note that our performance measure ignores the extra cost of computing the heuristic values; the next subsection describes a method that makes this cost manageable. The MRV heuristic doesn’t help at all in choosing the first region to color in Australia, DEGREE HEURISTIC because initially every region has three legal colors. In this case, the degree heuristic comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. In Figure 5.1, SA is the variable with highest degree, 5; the other variables have degree 2 or 3, except for T, which has 0. In fact, once SA is chosen, applying the degree heuristic solves the problem without any false steps—you can choose any consistent color at each choice point and still arrive at a solution with no backtracking. The minimum remaining values heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker. Once a variable has been selected, the algorithm must decide on the order in which to examine its values. For this, the least-constraining-value heuristic can be effective in some LEASTCONSTRAININGVALUE cases. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. For example, suppose that in Figure 5.1 we have generated the partial assignment with WA = red and NT = green, and that our next choice is for Q. Blue would be a bad choice, because it eliminates the last legal value left for Q’s neighbor, SA. The least-constraining-value heuristic therefore prefers red to blue. In general, the heuristic is trying to leave the maximum flexibility for subsequent variable assignments. Of course, if we are trying to find all the solutions to a problem, not just the first one, then the ordering does not matter because we have to consider every value anyway. The same holds if there are no solutions to the problem. Propagating information through constraints So far our search algorithm considers the constraints on a variable only at the time that the variable is chosen by SELECT-UNASSIGNED-VARIABLE. But by looking at some of the constraints earlier in the search, or even before the search has started, we can drastically reduce the search space. Forward checking One way to make better use of constraints during search is called forward checking. When- FORWARD CHECKING ever a variable X is assigned, the forward checking process looks at each unassigned variable Y that is connected to X by a constraint and deletes from Y ’s domain any value that is inconsistent with the value chosen for X. Figure 5.6 shows the progress of a map-coloring search with forward checking. There are two important points to notice about this example. First, notice that after assigning WA = red and Q = green, the domains of NT and SA are reduced to a single value; we have eliminated branching on these variables altogether by propagating information from WA and Q. The MRV heuristic, which is an obvious partner for forward checking, would automatically select SA and NT next. (Indeed, we can view forward checking as an efficient way to incrementally compute the information that the