COMP30024 Artificial Intelligence
Week 8 Problem Sheet
Weekly Topic Review
Backtracking refers to a general method of building sequence of decisions to solve a graph problem incrementally. Suppose we have a partial solution to a problem we would like to extend: A = (a1, a2, . . . ak). To choose next solution component, ak+1:
Copyright By PowCoder代写 加微信 powcoder
• Recursively evaluate every possibility consistent with past decisions. When we establish that a partial solution cannot be extended into a complete solution, or is worse than the current best solution, we terminate the recursive call, thereby pruning regions of state space from the search tree which cannot contain a solution (or an optimal solution if we have some notion of optimality). We backtrack to the deepest node with unexpanded children and invoke recursion again.
• Choose a valid successor (or the ’best’ one if we have an optimality criterion), A ← A ak+1. Repeat until A becomes a complete solution.
This is implemented as depth-first/recursive traversal with additional logic at each call that helps narrow the search space, using problem constraints to prune subtrees as early as possible1.
def backtrack_dfs(A, k):
if A = (a_1, a_2, …, a_k) is a solution:
# Enumerate all possible candidates extending deepest partial solution
candidate_queue = construct_candidates(A, k)
# While valid children exist, extend solution by recursion.
while candidate_queue is not None:
A[k] = candidate_queue.pop() # add current candidate to A
result = backtrack_dfs(A, k)
1The pseudo-code hopefully makes it clear that backtracking is just DFS with added pruning logic. 1
if result != failure; return result
A[k] = null # backtrack; remove candidate from A
return failure
Constraint Satisfaction Problems
A constraint satisfaction problem (CSP) is an example of an identification problem, where we want to arrive at a goal state without regard to any notion of optimality. We define the CSP in terms of:
• A set of variables X = {X1, . . . Xn}. Each variable assumes values in its respective domain, D = {D1,…,Dn}
• Constraints C expressing restrictions on the domain of individual variables, when considering relationships between variables. For the case of binary constraints, we can represent a CSP as a graph (V,E) where the vertices are the variables and the edges are constraints between pairs of variables.
The CSP is solved when values are assigned to all variables in X without violating the given constraints. The basic idea is to eliminate large regions of search space by identifying combinations of variables/values that violate constraints, then pruning appropriately – this is just backtracking!
A classic example of a CSP is the n-Queens problem (Figure 1). Given an n × n chessboard, a valid solution is a placement of n queens on the board, so that no queen can capture any other queen. The obvious backtracking strategy was first reported by Gauss in the 1800s:
• Place queens on board one at a time, start with row r = 0.
• To place r-th queen, try all possible squares in row r. If attacked by an earlier queen, pass,
otherwise place.
• Continue recursively, backtracking up the tree at dead-ends.
Figure 1 visualizes the associated 4-Queens recursion tree – each node represents a recursive sub- problem, edges correspond to recursion calls, and leaves correspond to dead-end partial solutions if r < n and full solutions if r = n.
Solving CSPs
Constraint satisfaction problems are NP-hard - there exists no known algorithm for finding solutions to them in polynomial time. This can be attributed to the fact that for an n-variable problem with maximal domain size d, there are an exponential number of possible assignments, O(dn), we have to
miliar with the rules of chess, this means that no two queens
w, the same column, or the same diagonalà
with r = 0 à Edges in the recursion tree correspond to recursive callsà Leaves
correspond to partial solutions that cannot be further extended, either because
there is already a queen on every row, or because every position in the next
empty row is attacked by an existing queenà The backtracking search for complete solutions is equivalent to a depth-Þrst search of this treeà
Figure .. The complete recursion tree of Gauss and Laquière’s algorithm for the queens problem. Figure 1: Left: Valid 8-Queens configuration. Right: Recursion tree for 4-Queens.
tsolutiontothe8queensproblem,representedbythearray 5,7,1,4,2,8,6,3
ten to his friend in , the eminent
sift through to find a satisfactory assignment. Nevertheless, CSPs tend to have more structure than
generic graph search problems, allowing us to use various heuristic methods to often find solutions in an acceptable amount of time.
rl wrote that one could easily conÞrm Franz
t the EWiegwhiltl ilQlusutreatenexsampprleos bofltehmese heuarsisti cs ussinogltuhetimoanp-scolbouyrintgrpiraolbleamnfdrom lectures, where
ursà ÒSchwer ist es übrigens nicht, durch ein methodisches
of nodes can significantly reduce runtime. The following heuristics decide which variable to assign
no adjacent states may be assigned the same colour. Much like alpha-beta search, a good ordering
se Gewissheit zu verscha en, wenn man oder ein paar Stunden
next based on the current partial solution. The basic premise is to detect inevitable failure as soon
Ó HisdescriptionTatonnirencomesfromtheFrenchtâtonner, rope, or fumble around blindly, as if in the darkà
as possible while exploring the regions of the graph where a solution is most likely to exist.
• Minimum RemaininMg VinaliumesuHmeuriestmicaining values described the following recursive strategy for solving the
– Choose successor with the fewest legal values. Selects successor states that are more Minimum remaining values (MRV):
à the same strategy was described in by the French
likely to result in failure (end as dead leaves of recursion tree).
choose the variable with the fewest legal values
ematician ¬douard Lucas, who attributed the method to
reà We place queens on the board one row at a time, starting
To place the rth queen, we methodically try all n squares in
right in a simple for loopà If a particular square is attacked by
e ignore •thDaetgrseqeuHaerueriàstoictherwise, we tentatively place a queen
recursively grope for consistent placements of the queens in
– Choose successor involved in the largest number of constraints on other potential suc-
cessors. More constraints → lower branching factor of recursion subtree. s the resulting algorithm, which recursively enumerates all
s solutions that are consistent with a given partial solutionà we represent the positions of the queens using an array
i indicates which square in row i contains a queenà When
Tie-breaker among MRV variables
Degree heuristic:
choose the variable with the most constraints on remaining variables
• Least Constraining Value
– Given a variable, assign the value that makes the fewest choices of variables for neigh-
Least constraining value
bouring candidates illegal.
– This permits the maximum remaining flexibility for remaining variables, making it more
Given a variable, choose the least constraining value:
likely to find a complete solution in future.
the one that rules out the fewest values in the remaining variables
Allows1valuCehapfoter5SA20
Allows 0 values for SA
Combining these heuristics makes 1000 queens feasible
Finally, we discuss filtering over a CSP, which is not a solution method, but yields a pruned search graph which is faster to traverse. The basic idea is to use local constraints to eliminate illegal variable assignments, by pruning values of the domain for each variable that violate binary constraints. This leads us to the Arc-consistency 3 (AC-3) algorithm (Figure 2), which we briefly sketch below. Define an arc as a directed edge in the constraint graph in a CSP. The constraint graph is undirected, but we interpret an undirected edge as two directed edges pointing in opposite directions:
Chapter 5 21
• A CSP variable is arc-consistent if every value in its domain satisfies all relevant binary constraints.
• For X, Y variables involved in a constraint, X → Y arc-consistent if every value X = x has legal assignment Y = y satisfying the constraint on (X, Y ).
• The AC-3 algorithm enumerates all possible arcs in a queue Q and makes Xi arc-consistent w.r.t Xj by reducing the domains of variables accordingly.
• If Di unchanged, move onto next arc. Otherwise append all arcs (Xk, Xi) where Xk is adjacent to Xi, to the queue.
• If domain Di is reduced to 0, the CSP has no consistent solution.
• AC-3 is not a solution method, but defines an equivalent problem that is faster to traverse
via backtracking, as the variables have smaller domains. 4
Arc consistency algorithm
function AC-3( csp) returns the CSP, possibly with reduced domains inputs: csp, a binary CSP with variables {X1, X2, . . . , Xn}
local variables: queue, a queue of arcs, initially all the arcs in csp
while queue is not empty do
(Xi, Xj)←Remove-First(queue)
if Remove-Inconsistent-Values(Xi, Xj) then
for each Xk in Neighbors[Xi] do add (Xk, Xi) to queue
function Remove-Inconsistent-Values( Xi, Xj) returns true iff succeeds removed ← false
for each x in Domain[Xi] do
if no value y in Domain[Xj] allows (x,y) to satisfy the constraint Xi ↔ Xj thendeletexfromDomain[Xi]; removed←true
return removed
O n2d3 , can be reduced to O n2d2 (but detecting all is NP-hard) Figure 2 Chapter 5 31
1. n-Queens [T] The n-Queens problem is a classic benchmark search problem. Given an n × n chessboard, the aim is to place a total of n queens on the board, so that no queen can capture any other queen.
(a) Derive a nontrivial upper bound on the size of the state space for general n.
(b) Develop a CSP formulation for this problem. Specify the relevant variables together with
their domains, and the constraints between relevant variables.
(c) Design an algorithm, in pseudo-code, that counts the number of valid n-Queens config-
urations using backtracking. Hint: Use DFS.
2. Apparent paradox [T] Explain why it is a good heuristic to choose the variable that is most
constrained but the value that is least constraining in a CSP search.
3. Aussie-3 [T] Use the AC-3 algorithm to show that arc consistency can detect the inconsistency of the partial assignment {WA = Green, V = Red} for the problem of colouring the map of Australia in Figure 3.
4. AC-Tree [T] What is the time complexity of running the AC-3 arc consistency algorithm on a tree-structured CSP? Give your answer in terms of the number of edges on the constraint graph, E, and the maximum possible domain size, D.
inputs: csp , a CSP with components X, D, C
n ← number of variables in X assignment ← an empty assignment root ← any variable in X
X ←TOPOLOGICALSORT(X,root) forj =n downto2do
MAKE-ARC-CONSISTENT(PARENT(Xj),Xj)
if it cannot be made consistent then return failure for i = 1 to n do
assignment [Xi ] ← any consistent value from Di
if there is no consistent value then return failure return assignment
Figure 6.11 The TREE-CSP-SOLVER algorithm for solving tree-structured CSP has a solution, we will find it in linear time; if not, we will detect a contrad
(b) Figure 6.12 (a) The original constraint graph from Figure 6.1. (b) The con
after the removal of SA.
deleting from the domains of the other variables any values that are incon value chosen for SA.
Now, any solution for the CSP after SA and its constraints are remov sistent with the value chosen for SA. (This works for binary CSPs; the sit complicated with higher-order constraints.) Therefore, we can solve the rem the algorithm given above and thus solve the whole problem. Of course, in t (as opposed to map coloring), the value chosen for SA could be the wrong on need to try each possible value. The general algorithm is as follows:
Figure 3: Map-colouring constraint graph.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com