我目前正在尝试为一个大学项目编写一个回溯解析器。它应该解决作业调度问题。我创建了 2 个类来执行此操作:JobSchedulingProblem 和 Constraint。
class JobSchedulingProblem:
def __init__(self):
self.constraints = constrs.constraint()
self.variables={}
def checkAllconstraints(self,assignment) ->bool:
for var1,var2 in self.constraints.constraints:
result=self.check_constraint(var1,var2, assignment)
if not result:
return False
return True
def check_constraint(arg1,arg2,self,assignment) ->bool:
if (self.variables[arg1] not in assignment) or (self.variables[arg2] not in assignment):
return True
if self.constraints.constraints[arg1][arg2][1]==0:
return assignment[arg2]>=assignment[arg1]+self.constraints.constraints[arg1][arg2][0]
if self.constraints.constraints[arg1][arg2][1]==1:
return assignment[arg1]+self.constraints.constraints[arg1][arg2][0]<=assignment[arg2]
if self.constraints.constraints[arg1][arg2][1]==2:
return (assignment[arg1]+self.constraints.constraints[arg1][arg2][0]<=assignment[arg2])or(assignment[arg2]+self.constraints.constraints[arg1][arg2][0]<=assignment[arg1])
def add_variable(self, var, domain):
self.variables[var] = domain
print (self.variables.keys())
def add_constraint(self, arg1,arg2, value, type, assignment):
self.constraints.constraints[arg1][arg2]=(value,type)
if type==1:
self.constraints.constraints[arg2][arg1]=(value,0)
if type==0:
self.constraints.constraints[arg2][arg1]=(value,1)
else:
self.constraints.constraints[arg2][arg1]=(value,2)
def removeDomains(new_assignment, var,self):
removeddomains={}
for var1 in self.constraints.constraints[var]:
if self.constraints.constraints[var][var1][1]==0:
intervallo_da_rimuovere = range(1, new_assignment+1-self.constraints.constraints[var][var1][0])
# crea un nuovo range escludendo l'intervallo specificato
nuovo_dominio = list(self.variables[var1])
nuovo_dominio = list(filter(lambda x: x not in intervallo_da_rimuovere, nuovo_dominio))
self.variables[var1] = range(nuovo_dominio[0], nuovo_dominio[-1] + 1)
removeddomains[var1]=intervallo_da_rimuovere
if (self.constraints.constraints[var][var1][1]==1) or (self.constraints.constraints[var][var1][1]==2):
intervallo_da_rimuovere = range(1, new_assignment+1+self.constraints.constraints[var][var1][0])
# crea un nuovo range escludendo l'intervallo specificato
nuovo_dominio = list(self.variables[var1])
nuovo_dominio = list(filter(lambda x: x not in intervallo_da_rimuovere, nuovo_dominio))
self.variables[var1] = range(nuovo_dominio[0], nuovo_dominio[-1] + 1)
removeddomains[var1]=intervallo_da_rimuovere
return removeddomains
def putRemovedDomains(tmp, var,self):
for var1 in self.constraints.constraints[var]:
lista1 = list(tmp[var1])
lista2 = list(self.variables[var1])
lista_unione = lista1 + lista2
# Crea un nuovo range basato sulla lista unione
self.variables[var1] = range(lista_unione[0], lista_unione[-1] + 1)
def backtracking_search(self, assignment={}):
if len(assignment) == len(self.variables):
return assignment
var_not_assigned = [var for var in self.variables if var not in assignment]
var = var_not_assigned[0]
for value in self.variables[var]:
new_assignment = assignment.copy()
new_assignment[var] = value
if self.checkAllconstraints( new_assignment):
tmp = self.removeDomains(new_assignment, var, self)
result = self.backtracking_search(self, new_assignment)
if result is None:
self.putRemovedDomains(tmp,var,self)
if result is not None:
return result
return None
class constraint:
constraints={}
def __init__(self):
self.constraints = {
'Aa': {},
'Ap': {},
'Rda': {},
'Rsa': {},
'Rdp': {},
'Rsp': {},
'Dda': {},
'Dsa': {},
'Ddp': {},
'Dsp': {},
'Cda': {},
'Csa': {},
'Cdp': {},
'Csp': {},
'I': {},
}
self.constraints['Aa']['Rda']=(10,1)
self.constraints['Aa']['Rsa']=(10,1)
self.constraints['Ap']['Rdp']=(10,1)
self.constraints['Ap']['Rdp']=(10,1)
self.constraints['Rda']['Dda']=(1,1)
self.constraints['Dda']['Cda']=(2,1)
self.constraints['Rsa']['Dsa']=(1,1)
self.constraints['Ddp']['Cdp']=(2,1)
self.constraints['Rsp']['Dsp']=(1,1)
self.constraints['Dsp']['Csp']=(2,1)
self.constraints['Aa']['Ap']=(10,2)
self.constraints['Ap']['Aa']=(10,2)
self.constraints['Aa']['I']=(3,1)
self.constraints['Ap']['I']=(3,1)
self.constraints['Rda']['I']=(3,1)
self.constraints['Dda']['I']=(3,1)
self.constraints['Cda']['I']=(3,1)
self.constraints['Rsa']['I']=(3,1)
self.constraints['Dsa']['I']=(3,1)
self.constraints['Csa']['I']=(3,1)
self.constraints['Rdp']['I']=(3,1)
self.constraints['Ddp']['I']=(3,1)
self.constraints['Cdp']['I']=(3,1)
self.constraints['Rsp']['I']=(3,1)
self.constraints['Dsp']['I']=(3,1)
self.constraints['Csp']['I']=(3,1)
self.constraints['I']['Aa']=(3,0)
self.constraints['I']['Ap']=(3,0)
self.constraints['I']['Rda']=(3,0)
self.constraints['I']['Dda']=(3,0)
self.constraints['I']['Cda']=(3,0)
self.constraints['I']['Rsa']=(3,0)
self.constraints['I']['Dsa']=(3,0)
self.constraints['I']['Csa']=(3,0)
self.constraints['I']['Rdp']=(3,0)
self.constraints['I']['Ddp']=(3,0)
self.constraints['I']['Cdp']=(3,0)
self.constraints['I']['Rsp']=(3,0)
self.constraints['I']['Dsp']=(3,0)
self.constraints['I']['Csp']=(3,0)
self.constraints['Rda']['Aa']=(10,0)
self.constraints['Rsa']['Aa']=(10,0)
self.constraints['Rdp']['Ap']=(10,0)
self.constraints['Rsp']['Ap']=(10,0)
self.constraints['Dda']['Rda']=(1,0)
self.constraints['Cda']['Dda']=(2,0)
self.constraints['Dsa']['Rsa']=(1,0)
self.constraints['Csa']['Dsa']=(2,0)
self.constraints['Ddp']['Rdp']=(1,0)
self.constraints['Cdp']['Ddp']=(2,0)
self.constraints['Dsp']['Rsp']=(1,0)
self.constraints['Csp']['Dsp']=(2,0)
在尝试运行它时,我遇到了 2 个错误:
发生异常:AttributeError “str”对象没有属性“变量” 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 15 行,在 check_constraint 中 if (self.variables[arg1] 不在赋值中) 或 (self.variables[arg2] 不在赋值中): 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 9 行,在 checkAllconstraints 中 结果=self.check_constraint(var1,var2,赋值) 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 79 行,位于 backtracking_search 如果 self.checkAllconstraints( new_assignment): 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 114 行,在 main 中 解决方案 = csp.backtracking_search() 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 149 行,位于 主要的() 属性错误:“str”对象没有属性“变量”
或
发生异常:TypeError JobSchedulingProblem.check_constraint() 需要 4 个位置参数,但给出了 5 个 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 9 行,在 checkAllconstraints 中 结果= self.check_constraint(var1,var2,self,赋值) 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 79 行,位于 backtracking_search 如果 self.checkAllconstraints( new_assignment): 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 114 行,在 main 中 解决方案 = csp.backtracking_search() 文件“/home/alebonch/Python/Progetto IA/Backtrackjobscheduling.py”,第 149 行,位于 主要的() TypeError:JobSchedulingProblem.check_constraint() 需要 4 个位置参数,但给出了 5 个
当我尝试改变时:
result=self.check_constraint(var1,var2, assignment)
进入:
result=self.check_constraint(var1,var2, self, assignment)
我尝试向chatGPT寻求帮助,但我对变量如何变成字符串以及编辑认为我传递的参数比我应该做的更多这一事实感到非常困惑。这是我第一次用 python 编程,我可能犯了很多错误,任何帮助将不胜感激。
self
,它是您调用该函数的类的实例。所有类函数(例如
check_constraint()
)都应将
self
作为第一个参数,这样就不会造成混淆,但是当您在类的实例上调用该函数(例如
my_instance_of_JobSchedulingProblem.check_constraint()
)时,您会跳过
self
争论。我认为通过将
self
作为所有函数的第一个参数可以解决你的两个错误。