COMP30024 Artificial Intelligence
Week 8 Problem Sheet Solutions
• Tutors: These are not unique, complete (and definitely not optimally pedagogical) solutions. there are other ways of deriving these results and the way you prefer is to some extent an aesthetic judgement.
• Students: If you want to attain any benefit from the problems you should make a genuine attempt at them before you see the solutions.
Copyright By PowCoder代写 加微信 powcoder
Comments/corrections are as always greatly appreciated by the teaching team.
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.
• Stupid: 2n2 (n2 squares, 2 possible states for each).
• Very Very Bad: n2 = n2! (Permutations of n queens on n × n board). n (n2 −n)!n!
• Very Bad: nn (1 queen per row)
• Bad: n! (1 queen per row and column)
• Ok: n(n − 2)(n − 4)… = ⌈n/2⌉−1(n − 2i). (Each queen eliminates at least two i=0
squares in next row).
• Good: ??? No known formula for the exact number of solutions – but asymptotic
bounds recently found in (Simkin, 2021)!
(b) Develop a CSP formulation for this problem. Specify the relevant variables together with
their domains, and the constraints between relevant variables.
• Variables: Position of queen in row r.
• Represent positions of queens through array Q[1, . . . , n]. Element r of the array,
Q[r], indicates the position of the queen in row r.
• Domain: Q[r] ∈ {1,…,n}.
• Constraints:
– Let i ̸= j be row indexes.
– Q[i] ̸= Q[j] (Same column placement forbidden).
– |Q[j] − Q[i]|≠ |j − i| (Diagonal placement forbidden).
• Constraint graph?
– Nodes: Variables Q[i].
– Edges represent constraints between variables. Every queen can theoretically attack every other queen on the chessboard – so our constraint graph is a clique; we have an edge connecting every pair of variables in the CSP. In n-Queens it suffices to consider binary constraints as the queen in row i independently threatens the queens in rows j, k.
(c) Design an algorithm, in pseudo-code, that counts the number of valid n-Queens config- urations using backtracking. Hint: Use DFS.
def nQueens(Q: List[int], r: int) -> int:
# Q: vector holding column indices for queen assignments.
# r: Row index for recursion.
if r == n:
solutions = 0
for i in range(n):
# Check if placement is legal, given previous placements
legal = True
for j in range(r):
# i loops over the proposed placement column
if (Q[j] == i) or (abs(Q[j] – i) == (r-j)):
legal = False
# STOP!!!!!!! – Prune!
# If legal, extend recursively
solutions += nQueens(Q. r+1)
return solutions
Q = [None for _ in range(n)]
return nQueens(Q,0)
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.
• The search tree for solutions grows exponentially, but most branches are invalid combi- nations of assignments.
• The Minimum Remaining Values (MRV) heuristic chooses the variable most likely to cause a failure – if search fails early, backtrack and prune the search space. If the current partial solution cannot be expanded into a complete solution, is it better to know earlier instead of wasting time searching exponentially many dead-ends.
• Because we need to find a single solution, we want to be generous and select the value that allows the most future assignments to avoid conflict. This makes it more likely the search will find a complete solution.
• This asymmetry makes it better to use MRV to prune exponentially growing search space by choosing least-promising successors first, but increase the probability of success for all successors via the least constraining value heuristic.
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 1.
• Wish to color states such that no neighbouring states share the same color.
• To detect inconsistency, reduce the domain of some variable in graph to zero =⇒ no
possible color assignments for that variable.
• Initial variable domains:
– NT ={R,G,B}
– SA={R,G,B}
– Q={R,G,B}
– NSW ={R,G,B}
• Pop WA-SA arc from queue (degree heuristic). – SA={R,B}
• Pop SA-V arc from queue. – SA={B}
• PopNT−WA.
– NT ={R,B}
• PopNT−SA.
– NT = {R} • Pop NT-Q:
– Q={G,B} • Pop SA-Q:
• No legal assignment for NSW, CSP is inconsistent, terminate.
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.
• A tree-structured CSP has no loops in the constraint graph. We first choose an arbitrary node to serve as the root, convert all undirected edges to directed edges pointing away from the root, and then topologically sort the resulting directed acyclic graph using the methods you learnt in Week 3.
• Make the resulting graph directed arc-consistent by performing a backward pass from the tail to the root, enforcing arc consistency for all arcs Parent(Xi) → Xi. This will prune the domain of the variables in the constraint graph. Throw a failure value if this is not possible.
• Now start at the root, and perform a forward assignment using standard backtracking. But note we already enforced arc-consistency on all the arcs, so irrespective of the assign- ment we choose for any given node, there will be at least one consistent assignment to all its children, guaranteeing a solution. Hence this step never actually has to backtrack.
• Checking consistency requires O(D2) operations (pairwise comparison), and no arc must be considered more than once in the absence of backtracking, for a worst-case runtime of O(ED2).
References
Michael Simkin. The number of n-queens configurations. arXiv preprint arXiv:2107.13460, 2021.
MAKE-ARC-CONSISTENT(PARENT(X ), X )
n the algorithm given above and thus solve the whole problem.
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 solvin CSP has a solution, we will find it in linear time; if not, we wil
Figure 1: Map-colouring constraint graph.
Figure 6.12 (a) The original constraint graph from Figure after the removal of SA.
deleting from the domains of the other variables any values value chosen for SA.
Now, any solution for the CSP after SA and its constr sistent with the value chosen for SA. (This works for binar
complicated with higher-order constraints.) Therefore, we ca
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com