-
Notifications
You must be signed in to change notification settings - Fork 0
/
csp.py
230 lines (181 loc) · 7.84 KB
/
csp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
from utils import argmin_random_tie, count, first
import search
class CSP(search.Problem):
def __init__(self, variables, domains, neighbors, constraints):
"Construct a CSP problem. If variables is empty, it becomes domains.keys()."
variables = variables or list(domains.keys())
self.variables = variables
self.domains = domains
self.neighbors = neighbors
self.constraints = constraints
self.initial = ()
self.curr_domains = None
self.nassigns = 0
def assign(self, var, val, assignment):
"Add {var: val} to assignment; Discard the old value if any."
assignment[var] = val
self.nassigns += 1
def unassign(self, var, assignment):
"""Remove {var: val} from assignment.
DO NOT call this if you are changing a variable to a new value;
just call assign for that."""
if var in assignment:
del assignment[var]
def nconflicts(self, var, val, assignment):
"Return the number of conflicts var=val has with other variables."
# Subclasses may implement this more efficiently
def conflict(var2):
return (var2 in assignment and not self.constraints(var, val, var2, assignment[var2]))
return count(conflict(v) for v in self.neighbors[var])
def display(self, assignment):
"Show a human-readable representation of the CSP."
# Subclasses can print in a prettier way, or display with a GUI
print('CSP:', self, 'with assignment:', assignment)
# These methods are for the tree- and graph-search interface:
def actions(self, state):
"""Return a list of applicable actions: nonconflicting
assignments to an unassigned variable."""
if len(state) == len(self.variables):
return []
else:
assignment = dict(state)
var = first([v for v in self.variables if v not in assignment])
return [(var, val) for val in self.domains[var]
if self.nconflicts(var, val, assignment) == 0]
def result(self, state, action):
"Perform an action and return the new state."
(var, val) = action
return state + ((var, val),)
def goal_test(self, state):
"The goal is to assign all variables, with all constraints satisfied."
assignment = dict(state)
return (len(assignment) == len(self.variables)
and all(self.nconflicts(variables, assignment[variables], assignment) == 0
for variables in self.variables))
# These are for constraint propagation
def support_pruning(self):
"""Make sure we can prune values from domains. (We want to pay
for this only if we use it.)"""
if self.curr_domains is None:
self.curr_domains = {v: list(self.domains[v]) for v in self.variables}
def suppose(self, var, value):
"Start accumulating inferences from assuming var=value."
self.support_pruning()
removals = [(var, a) for a in self.curr_domains[var] if a != value]
self.curr_domains[var] = [value]
return removals
def prune(self, var, value, removals):
"Rule out var=value."
self.curr_domains[var].remove(value)
if removals is not None:
removals.append((var, value))
def choices(self, var):
"Return all values for var that aren't currently ruled out."
return (self.curr_domains or self.domains)[var]
def infer_assignment(self):
"Return the partial assignment implied by the current inferences."
self.support_pruning()
return {v: self.curr_domains[v][0]
for v in self.variables if 1 == len(self.curr_domains[v])}
def restore(self, removals):
"Undo a supposition and all inferences from it."
for B, b in removals:
self.curr_domains[B].append(b)
# This is for min_conflicts search
def conflicted_vars(self, current):
"Return a list of variables in current assignment that are in conflict"
return [var for var in self.variables
if self.nconflicts(var, current[var], current) > 0]
def AC3(csp, queue=None, removals=None):
"""[Figure 6.3]"""
if queue is None:
queue = [(Xi, Xk) for Xi in csp.variables for Xk in csp.neighbors[Xi]]
csp.support_pruning()
while queue:
(Xi, Xj) = queue.pop()
if revise(csp, Xi, Xj, removals):
if not csp.curr_domains[Xi]:
return False
for Xk in csp.neighbors[Xi]:
if Xk != Xi:
queue.append((Xk, Xi))
return True
def revise(csp, Xi, Xj, removals):
"Return true if we remove a value."
revised = False
for x in csp.curr_domains[Xi][:]:
# If Xi=x conflicts with Xj=y for every possible y, eliminate Xi=x
if all(not csp.constraints(Xi, x, Xj, y) for y in csp.curr_domains[Xj]):
csp.prune(Xi, x, removals)
revised = True
return revised
# ______________________________________________________________________________
# CSP Backtracking Search
# Variable ordering
def first_unassigned_variable(assignment, csp):
"The default variable order."
return first([var for var in csp.variables if var not in assignment])
def mrv(assignment, csp):
"Minimum-remaining-values heuristic."
return argmin_random_tie(
[v for v in csp.variables if v not in assignment],
key=lambda var: num_legal_values(csp, var, assignment))
def num_legal_values(csp, var, assignment):
#if csp.curr_domains:
#return len(csp.curr_domains[var])
#else:
return count(csp.nconflicts(var, val, assignment) == 0
for val in csp.domains[var])
# Value ordering
def unordered_domain_values(var, assignment, csp):
"The default value order."
return csp.choices(var)
def lcv(var, assignment, csp):
"Least-constraining-values heuristic."
return sorted(csp.choices(var),
key=lambda val: csp.nconflicts(var, val, assignment))
# Inference
def no_inference(csp, var, value, assignment, removals):
return True
def forward_checking(csp, var, value, assignment, removals):
"Prune neighbor values inconsistent with var=value."
for B in csp.neighbors[var]:
if B not in assignment:
for b in csp.curr_domains[B][:]:
if not csp.constraints(var, value, B, b):
csp.prune(B, b, removals)
if not csp.curr_domains[B]:
return False
return True
def mac(csp, var, value, assignment, removals):
"Maintain arc consistency."
return AC3(csp, [(X, var) for X in csp.neighbors[var]], removals)
# The search, proper
def backtracking_search(csp: CSP,
select_unassigned_variable=first_unassigned_variable,
order_domain_values=unordered_domain_values,
inference=no_inference):
"""[Figure 6.5]
"""
def backtrack(assignment):
# Check that assignment is complete
if len(assignment) == len(csp.variables):
return assignment
# select variable not in assignment
var = select_unassigned_variable(assignment, csp)
for value in order_domain_values(var, assignment, csp):
# check if A is valid assignment
if 0 == csp.nconflicts(var, value, assignment):
csp.assign(var, value, assignment)
removals = csp.suppose(var, value)
if inference(csp, var, value, assignment, removals):
result = backtrack(assignment)
if result is not None:
return result
csp.restore(removals)
csp.unassign(var, assignment)
return None
result = backtrack({})
assert result is None or csp.goal_test(result)
# print(result)
return result