Error with inference (Backtrack algorithms and Job scheduling problem)

64 views Asked by At

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.

0

There are 0 answers