Im currently trying to program a Backtrack resolver using the mantaining arc consistency technique to do inferences on the domains of the other variables but Im stuck because it seems like I cant do the inference with variables not immediately linked to the variable Im trying to assign.
I have created 2 classes: a problem class and a constraint class.
Here's the code:
import constrs
class JobSchedulingProblem:
def __init__(self):
self.constraints = constrs.constraint()
self.variables={}
def checkAllconstraints(self,assignment) ->bool:
for var1 in self.constraints.constraints:
for var2 in self.constraints.constraints[var1]:
result=self.check_constraint(var1,var2, assignment)
if not result:
return False
return True
def check_constraint(self,arg1,arg2,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
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(self,new_assignment, var2, var):
removeddomains={}
for var1 in self.constraints.constraints[var]:
if var1 in new_assignment:
if self.constraints.constraints[var][var1][1]==0:
intervallo_da_rimuovere = range(1, new_assignment[var1]-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):
intervallo_da_rimuovere = range(1, new_assignment[var1]+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))
if not len(nuovo_dominio) ==0:
self.variables[var1] = range(nuovo_dominio[0], nuovo_dominio[-1] +1 )
removeddomains[var1]=intervallo_da_rimuovere
else:
if self.constraints.constraints[var][var1][1]==0:
intervallo_da_rimuovere = range(1, new_assignment[var]-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[var]+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))
if not len(nuovo_dominio) ==0:
self.variables[var1] = range(nuovo_dominio[0], nuovo_dominio[-1] +1 )
removeddomains[var1]=intervallo_da_rimuovere
return removeddomains
def putRemovedDomains(self,tmp):
for var1 in self.constraints.constraints:
for var2 in self.constraints.constraints[var1]:
lista1 = list(tmp[var2])
lista2 = list(self.variables[var2])
lista_unione = lista1 + lista2
# Crea un nuovo range basato sulla lista unione
self.variables[var2] = range(lista_unione[0], lista_unione[-1] + 1)
def backtracking_search(self, assignment={}):
if len(assignment) == len(self.variables):
return assignment
print(str(len(assignment))+"^ backtrack")
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={}
for var1 in self.variables:
if var1 not in assignment:
tmp.update(self.removeDomains(new_assignment, var1,var))
print("Dopo l'inferenza di "+var1+":")
for var2 in self.variables:
print(var2+" :")
print(self.variables[var2])
result = self.backtracking_search( new_assignment)
if result is None:
self.putRemovedDomains(tmp,var,self)
if result is not None:
return result
return None
from typing import Any
import Backtrackjobscheduling
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"]["Rsp"]=(10,1)
self.constraints["Rda"]["Dda"]=(1,1)
self.constraints["Dda"]["Cda"]=(2,1)
self.constraints["Rsa"]["Dsa"]=(1,1)
self.constraints["Dsa"]["Csa"]=(2,1)
self.constraints["Rdp"]["Ddp"]=(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)
def main():
print("Arrivato a startare")
'''
c=constrs.constraint()
'''
# Esempio di utilizzo
print("Vincoli messi")
csp = JobSchedulingProblem()
# Definire variabili e domini
csp.add_variable("Aa", range(1,31))
csp.add_variable("Ap", range(1,31))
csp.add_variable("Rda", range(1,31))
csp.add_variable("Rsa", range(1,31))
csp.add_variable("Rdp", range(1, 31))
csp.add_variable("Rsp", range(1, 31))
csp.add_variable("Dda", range(1, 31))
csp.add_variable("Dsa", range(1, 31))
csp.add_variable("Ddp", range(1, 31))
csp.add_variable("Dsp", range(1, 31))
csp.add_variable("Cda", range(1, 31))
csp.add_variable("Csa", range(1, 31))
csp.add_variable("Cdp", range(1, 31))
csp.add_variable("Csp", range(1, 31))
csp.add_variable("I", range(1, 31))
print("Arrivato all'aggiungere le variabili")
# Risolvere il problema CSP
solution = csp.backtracking_search()
print(solution)
if __name__ == "__main__":
main()
I tried differentiating a bit the Removedomains() function but it didnt work out properly. The output Im expecting after the "first cycle of inferences" shouldnt be this:
Aa :
range(1, 31)
Ap :
range(11, 31)
Rda :
range(11, 31)
Rsa :
range(11, 31)
Rdp :
range(1, 31)
Rsp :
range(1, 31)
Dda :
range(1, 31)
Dsa :
range(1, 31)
Ddp :
range(1, 31)
Dsp :
range(1, 31)
Cda :
range(1, 31)
Csa :
range(1, 31)
Cdp :
range(1, 31)
Csp :
range(1, 31)
I :
range(4, 31)
I honestly dont know what Im doing wrong.