我正在尝试按照本页的代码和解释为约束满足问题(CSP(开发一个框架。我的 Python 版本是 2.7.13，所以我不得不稍微修改代码(我无法在这台计算机上进行更新或下载(。见下文：
from abc import ABCMeta
class abstractclassmethod(classmethod):
__isabstractmethod__ = True
def __init__(self, callable):
callable.__isabstractmethod__ = True
super(abstractclassmethod, self).__init__(callable)
class Constraint(object):
def __init__(self, variables):
self.variables = variables
@abstractclassmethod
def satisfied(self, assignment):
pass
class CSP(Constraint):
def __init__(self, variables, domains):
self.variables = variables
self.domains = domains
self.constraints = {}
for variable in self.variables:
self.constraints[variable] = []
if variable not in self.domains:
raise LookupError("Every variable should have a domain assigned to it")
def add_constraint(self, constraint):
for variable in constraint.variables:
if variable not in self.variables:
raise LookupError("Variable in constraint not in CSP")
else:
self.constraints[variable].append(constraint)
def consistent(self, variable, assignment):
for constraint in self.constraints[variable]:
if not constraint.satisfied(assignment):
return False
return True
def backtracking_search(self, assignment):
if len(assignment) == len(self.variables):
return assignment
for v in self.variables:
if v not in assignment:
unassigned.append(v)
first = unassigned[0]
for value in self.domains[first]:
local_assignment = assignment[:] # we make a copy
local_assignment[first] = value
if self.consistent(first, local_assignment):
result = self.backtracking_search(local_assignment)
if result is not None:
return result
return None
class MapColoringConstraint(Constraint):
def __init__(self, place1, place2):
self.place1 = place1
self.place2 = place2
super(Constraint, self).__init__()
def satisfied(sef, assignment):
if self.place1 not in assignment or self.place2 not in assignment:
return True
return assignment[self.place1] != assignment[self.place2]
我正在使用澳大利亚地图着色问题测试框架(如上面的链接所示(
if __name__ == "__main__":
variables = ["Western Australia", "Northern Territory", "South Australia",
"Queensland", "New South Wales", "Victoria", "Tasmania"]
domains = {}
for variable in variables:
domains[variable] = ['red', 'green', 'blue']
csp = CSP(variables, domains)
csp.add_constraint(MapColoringConstraint("Western Australia", "Northern Terriroty"))
csp.add_constraint(MapColoringConstraint("Western Australia", "South Australia"))
csp.add_constraint(MapColoringConstraint("South Australia", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Queensland", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
csp.add_constraint(MapColoringConstraint("New South Wales", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))
solution = csp.backtracking_search()
if solution is None:
print("No solution found!")
else:
print(solution)
我不断收到以下错误：
File 'csp.py', line 33, in add_constraint
for variable in constraint.variables:
AttributeError: 'MapColoringConstraint' object has no attribute 'variables'
除了一些修改，我的代码应该与网页上的代码相同。我似乎忽略了一些东西或删除了一些我不应该删除的东西。有人可以帮我找出缺少什么吗？
您在父级的 init(( 方法上对 super(( 方法的调用是问题所在super(Constraint, self).__init__()，这不会将父变量属性分配给子类，因此当add_constraint()方法尝试获取属性时，它会抛出您指示的错误。
你可以阅读更多关于python的继承层次结构来了解更多，这篇文章很好。
我已经对本文进行了一些引用并更新了代码，如下所示，它应该能够按预期运行。
# coding: utf-8
from abc import ABC, abstractmethod
class Constraint(ABC):
def __init__(self, variables):
self.variables = variables
@abstractmethod
def satisfied(self, assignment):
pass
class CSP():
def __init__(self, variables, domains):
self.variables = variables
self.domains = domains
self.constraints = {}
for variable in self.variables:
self.constraints[variable] = []
if variable not in self.domains:
raise LookupError(
'Every variable should have a domain assigned to it.')
def add_constraint(self, constraint):
for variable in constraint.variables:
if variable not in self.variables:
raise LookupError("Variable in constraint not in CSP")
else:
self.constraints[variable].append(constraint)
def consistent(self, variable, assignment):
for constraint in self.constraints[variable]:
if not constraint.satisfied(assignment):
return False
return True
def backtracking_search(self, assignment={}):
# assignment is complete if every variable is assigned (our base case)
if len(assignment) == len(self.variables):
return assignment
# get all variables in the CSP but not in the assignment
unassigned = [v for v in self.variables if v not in assignment]
first = unassigned[0]
for value in self.domains[first]:
local_assignment = assignment.copy()
local_assignment[first] = value
# if we're still consistent, we recurse (continue)
if self.consistent(first, local_assignment):
result = self.backtracking_search(local_assignment)
if result is not None:
return result
return None
class MapColoringConstraint(Constraint):
def __init__(self, place1, place2):
super().__init__([place1, place2])
self.place1 = place1
self.place2 = place2
def satisfied(self, assignment):
if self.place1 not in assignment or self.place2 not in assignment:
return True
return assignment[self.place1] != assignment[self.place2]
if __name__ == '__main__':
variables = [
"Western Australia", "Northern Territory", "South Australia",
"Queensland", "New South Wales", "Victoria", "Tasmania"
]
domains = {}
for variable in variables:
domains[variable] = ['red', 'green', 'blue']
csp = CSP(variables, domains)
csp.add_constraint(
MapColoringConstraint("Western Australia", "Northern Territory"))
csp.add_constraint(
MapColoringConstraint("Western Australia", "South Australia"))
csp.add_constraint(
MapColoringConstraint("South Australia", "Northern Territory"))
csp.add_constraint(
MapColoringConstraint("Queensland", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
csp.add_constraint(
MapColoringConstraint("New South Wales", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))
solution = csp.backtracking_search()
if solution is None:
print("No solution found!")
else:
print(solution)
示例运行
$ python csp.py
{'Western Australia': 'red', 'Northern Territory': 'green', 'South Australia': 'blue', 'Queensland': 'red', 'New South Wales': 'green', 'Victoria': 'red', 'Tasmania': 'green'}
$ python --version
Python 3.7.5