Backtracking and Lookhead Strategies

Backtracking and Lookhead Strategies

• If we apply BFS to generic CSP problems then we can notice that the branching factor at the top level is 'nd', because any of 'd' values can be assigned to any of 'n' variables. At the next level, the branching factor is '(n-1) d' and so on for n levels. Therfore a tree with 'n! * d' leaves is generated even though there are only 'dⁿ' possbile complete assignments.

Basic Steps in Backtracking Search

1. Depth-first search selects values for single variable at a given time.

2. Apply constraint to the variable when variable is selected.

3. Backtracking action-performed if a variable has no legal values left to assign.

4. Backtracking search is basic uninformed algorithm for CSPs.

Backtracking Search Algorithm

1. Consider a CSP problem.

2. Apply backtracking search. If backtracking search successful returns a solution else, a failure state which return a procedure recursive-backtracking.

3. Procedure recursive-backtracking starts with empty set and takes input as CSP problem.

If complete assignement possible or assignment done then return actual bs assignment.

4. Variable is assigned a specific value.

5. The relative constraint is a set which is taken as input.

6. If value is complete and consistent according to constraints then assign value to variable, add that to list.

7. Call the recursive backtracking until result or failure is reached..

8. Every time recursive-backtracking sustains result (i.e. assignment.)

9. If result is failure then remove variable with specific value from assignment. It will return failure status.

Limitations of Backtracking

1. A success function is generated with above algorithm. But backtracking is not effective for very large problems.

2. The general performance is not so good. Domain specific heuristic function combined with uninformed search algorithm can generate better searching result.

Improvement in Backtracking Search

We can also solve CSP without knowing the domain-specific knowledge. Here we need to design a module which resolve following queries:

1. Which variable is assigned in next step and what order values can be tried?

2. Impact of current variable assignments on unassigned variables.

3. Avoidance of known failed path in the potential paths.

Improvements of Backtracking

• Backtracking suffers from thrashing that is there is partial solutions that cannot be extended to a full solution and may be reprocessed several times (always leading to a dead end in the search space) To improve (practical) performance by preprocessing the search space underneath the currently selected variable improving (in a dynamic way) can be carried out. The search strategy can use either of the two schemes (related to the two phases of backtracking search), namely look-ahead and look-back strategy.

Look-ahead and look-back strategies

• Look-ahead strategy is invoked when next variable or next value is selected. For example: Which variable should be instantiated next? prefer variables that impose tighter constraints on the rest of the search space. Which value should be chosen for the next variable? maximize the number of options for future assignments

• Look-back strategy is invoked when the backtracking step is performed after reaching a dead end.

• For example: How deep should we backtrack? Also avoid irrelevant backtrack points (by analyzing reasons for the dead end and jumping back to the source of failure). How can we learn from dead ends? Record reasons for dead ends as new constraints so that the same inconsistencies can be avoided at later stages of the search.

Review Questions

1. Define constraint satisfaction problem and solve the following cryptarithmetic problem: FORTY + TEN + TEN SIXTY. (Refer section 6.1)

2. Define constraint satisfaction problem and solve the following cryptarithmetic problem: TWO + TWO = FOUR. (Refer section 6.1)

3. Write a backtracking search function for constraint satisfaction problem and write a map coloring representation as a constraint graph for the following figure. (Refer section 6.1)

4. Describe how to propagate information through constraints with example. (Refer section 6.3)

5. Explain the approaches for solving tree structured constraint satisfaction problem with suitable example. (Refer section 6.1)

6. Write the rule for generating propagating constraints for solving the given cryptarithmetic problem: SEND + MORE = MONEY. (Refer section 6.1)

7. Using CSP, explore the search space to solve the following cryptarithmatic problem.

TAKE

+ A

+ C A K E

KATE (Refer section 6.1)

8. Solve following cryptarithmetic using CSP

TOMATO + POTATO PUMPKIN (Refer section 6.1)

9. Solve the following crypt-arithmetic problem using constraint satisfaction method, LOGIC LOGIC PROLOG

You can assign unique single digit number from 0 to 9 to an alphabet. (Refer section 6.1)