“””Inference functions used with backtracking search.
COMP3620/6320 Artificial Intelligence
The Australian National University
Authors: COMP-3620 team
Date: 2021
Student Details
—————
Student Name: Peng Wang
Student Number: u6253304
Date: 05/05/2021
“””
import collections
from typing import Callable, Dict, List, Optional, Tuple
from csp import CSP
Assignment = Dict[str, str]
Pruned = List[Tuple[str, str]]
def forward_checking(var: str, assignment: Assignment, gamma: CSP) -> Optional[Pruned]:
“””Implement the forward checking inference procedure.
Parameters
———-
var : str
The name of the variable which has just been assigned.
assignment : Dict[str, str]
A Python dictionary of the current assignment. The dictionary maps
variable names to values. The function cannot change anything in
`assignment`.
gamma : CSP
An instance of the class CSP, representing the constraint network
to which we are looking for a solution. The function cannot change
anything in `gamma`.
Returns
——-
pruned_list : Optional[Pruned]
In the case that the algorithm detects a conflict, the assignment and
CSP should remain unchanged and the function should return None.
Otherwise, the algorithm should return a pruned_list, which is a list
of (variable, value) pairs that will be pruned out of the domains of
the variables in the problem. Think of this as the “edits” that are
required to be done on the variable domains.
“””
# *** YOUR CODE HERE ***
val = assignment[var]
conflicts = gamma.conflicts[(var, val)]
pruned_list = []
for conflict in conflicts:
if (conflict in gamma.neighbours[var]) and (not conflict in assignment):
vs = conflicts[conflict]
tmp = []
for v in vs:
if v in gamma.current_domains[conflict]:
pruned_list.append((conflict, v))
else:
tmp.append(v)
for v in tmp:
vs.remove(v)
return pruned_list
def arc_consistency(var: Optional[str], assignment: Assignment, gamma: CSP) -> Optional[Pruned]:
“””Implement the AC-3 inference procedure.
Parameters
———-
var : Optional[str]
The name of the variable which has just been assigned. In the case that
AC-3 is used for preprocessing, `var` will be `None`.
assignment : Dict[str, str]
A Python dictionary of the current assignment. The dictionary maps
variable names to values. The function cannot change anything in
`assignment`.
gamma : CSP
An instance of the class CSP, representing the constraint network
to which we are looking for a solution. The function cannot change
anything in `gamma`.
Returns
——-
pruned_list : Optional[Pruned]
In the case that the algorithm detects a conflict, the assignment and
CSP should remain unchanged and the function should return None.
Otherwise, the algorithm should return a pruned_list, which is a list
of (variable, value) pairs that will be pruned out of the domains of
the variables in the problem. Think of this as the “edits” that are
required to be done on the variable domains.
“””
# *** YOUR CODE HERE ***
if var is not None:
m = collections.deque()
pruned_list = []
val = assignment[var]
conflicts = gamma.conflicts[(var, val)]
assignment1 = {}
for conflict in conflicts:
m.append((conflict, var))
while m:
tmp = m.pop()
con = tmp[0]
var1 = tmp[1]
vals = assignment[var]
if var1 != var:
vals = assignment1[var1]
# remove
if (not (con, vals) in pruned_list) and (vals in gamma.current_domains[con]):
pruned_list.append((con, vals))
else:
continue
tt = len(gamma.current_domains[con]) – 1
if tt < 1: # conflict
return None
elif tt == 1:
vals = set(vals)
value = gamma.current_domains[con] - vals
value = str(value.pop())
con_new = gamma.conflicts[(con, value)]
assignment1[con] = value
# add new
for i in con_new:
m.append((i, con))
return pruned_list
else: # preprocessing
assignment1 = {}
pruned_list = []
for var_all in gamma.variables:
if not var_all in assignment1:
if len(gamma.current_domains[var_all]) == 1:
value_all = list(gamma.current_domains[var_all])
value_all = str(value_all.pop())
conflicts = gamma.conflicts[(var_all, value_all)]
assignment1[var_all] = value_all
m = collections.deque()
for conflict in conflicts:
m.append((conflict, var_all))
while m:
tmp = m.pop()
var1 = tmp[1]
con = tmp[0]
vals = assignment1[var1]
# remove
if (not (con, vals) in pruned_list) and (vals in gamma.current_domains[con]):
pruned_list.append((con, vals))
else:
continue
tt = len(gamma.current_domains[con]) - 1
if tt < 1: # conflict
return None
elif tt == 1:
vals = set(vals)
value = gamma.current_domains[con] - vals
value = str(value.pop())
con_new = gamma.conflicts[(con, value)]
assignment1[con] = value
# add new
for i in con_new:
m.append((i, con))
return pruned_list
# -------------------------------------------------------------------------------
# A function use to get the correct inference method for the search
# You do not need to touch this.
# -------------------------------------------------------------------------------
def get_inference_function(inference_type: str) -> Callable:
“””Return the function that does the specified inference.”””
if inference_type == “forward”:
return forward_checking
if inference_type == “arc”:
return arc_consistency
# If no inference is specified, we simply do nothing.
def no_inference(var, assignment, csp):
return []
return no_inference