Please help me check my python code for this question as follow:
Please follow the question from my attached image.
domains = {
'V1': [1, 2, 3,4],
'V2': [1, 2, 3,4],
'V3': [1, 2, 3,4],
'V4': [1, 2, 3,4],
'V5': [1, 2, 3,4],
'V6': [1, 2, 3,4],
'V7': [1, 2, 3,4],
'V8': [1, 2, 3,4]
}
constraints = {
('V8', 'V1'): lambda v8, v1: v8 <= v1,
('V1', 'V2'): lambda v1, v2: v1 < v2,
('V2', 'V4'): lambda v2, v4: v2 != v4,
('V2', 'V3'): lambda v2, v3: v2 == v3,
('V4', 'V5'): lambda v4, v5: v4 == v5,
('V3', 'V5'): lambda v3, v5: v3 < v5,
('V6', 'V3'): lambda v6, v3: v6 < v3,
('V6', 'V5'): lambda v6, v5: v6 != v5,
('V7', 'V3'): lambda v7, v3: v7 < v3,
('V7', 'V6'): lambda v7, v6: v7 <= v6,
('V1', 'V7'): lambda v1, v7: v1 <= v7,
('V8', 'V7'): lambda v8, v7: v8 == v7
}
def revise(x, y):
"""
Make variable `x` arc consistent with variable `y`.
To do so, remove values from `domains[x]` for which there is no
possible corresponding value for `y` in `domains[y]`.
Return True if a revision was made to the domain of `x`; return
False if no revision was made.
"""
revised = False
# Get x and y domains
x_domain = domains[x]
y_domain = domains[y]
# Get all arc (x, y) constraints
all_constraints = [
constraint for constraint in constraints if constraint[0] == x and constraint[1] == y]
for x_value in x_domain:
satisfies = False
for y_value in y_domain:
for constraint in all_constraints:
constraint_func = constraints[constraint]
if constraint_func(x_value, y_value):
satisfies = True
if not satisfies:
x_domain.remove(x_value)
revised = True
return revised
def ac3(arcs):
"""
Update `domains` such that each variable is arc consistent.
"""
# Add all the arcs to a queue.
queue = arcs[:]
# Repeat until the queue is empty
while queue:
# Take the first arc off the queue (dequeue)
(x, y) = queue.pop(0)
# Make x arc consistent with y
revised = revise(x, y)
# If the x domain has changed
if revised:
# Add all arcs of the form (k, x) to the queue (enqueue)
neighbors = [neighbor for neighbor in arcs if neighbor[1] == x]
queue = queue + neighbors
arcs = [ ('V8', 'V1'), ('V1', 'V2'), ('V2', 'V4'), ('V2', 'V3'), ('V4', 'V5'), ('V3', 'V5'), ('V6', 'V3'), ('V6', 'V5'), ('V7', 'V3'), ('V7', 'V6'), ('V1', 'V7'), ('V8', 'V7')]
ac3(arcs)
print(domains) #


0 comments