Optimization - Constraint Satisfaction Problem

 

Constraint Satisfaction Problem 

• Set of variables {X1, X2, ..., Xn} 

• Set of domains for each variable {D1, D2, ..., Dn} 

• Set of constraints C

Example;

There are many constraints:

·                     Hard constraint.

·                     Soft constraint.

·                     Unary constraint.

·                     Binary constraint.

SPs as Search Problems:

• initial state: empty assignment (no variables) 

• actions: add a {variable = value} to assignment 

• transition model: shows how adding an assignment changes the assignment 

• goal test: check if all variables assigned and constraints all satisfied 

• path cost function: all paths have same cost

Backtracking Search Algorithm:

function BACKTRACK(assignment, csp):

 if assignment complete: return assignment

 var = SELECT-UNASSIGNED-VAR(assignment, csp)

 for value in DOMAIN-VALUES(var, assignment, csp):

 if value consistent with assignment:

 add {var = value} to assignment

 result = BACKTRACK(assignment, csp)

 if result ≠ failure: return result

 remove {var = value} from assignment

 return failure

To solve this kind of problem we are using Python. Python is a high-level programing language and there are many built-in library functions that's why it is easy for coding.

This is the Artificial Intelligence course conducted by Nuruzzaman Faruqui at City University. This is the best Artificial Intelligence course in Bangladesh. Artificial intelligence is a lucrative field with above-average job growth, but the industry remains competitive. Roles in this discipline are very niche, requiring both an advanced technical background and extensive hands-on experience.

Problem Statement

We have to solve the problem so that every node is satisfied and there is no constraint.

The Python Code to Implement Constraint Satisfaction

In this problem, we are implementing to constraint satisfaction rule and backtracking rule to solve this problem.

Source Code:

"""
Naive backtracking search without any heuristics or inference.
"""

VARIABLES = ["A", "B", "C", "D", "E", "F", "G"]
CONSTRAINTS = [
    ("A", "B"),
    ("A", "C"),
    ("B", "C"),
    ("B", "D"),
    ("B", "E"),
    ("C", "E"),
    ("C", "F"),
    ("D", "E"),
    ("E", "F"),
    ("E", "G"),
    ("F", "G")
]


def backtrack(assignment):
    """Runs backtracking search to find an assignment."""

    # Check if assignment is complete
    if len(assignment) == len(VARIABLES):
        return assignment

    # Try a new variable
    var = select_unassigned_variable(assignment)
    for value in ["Monday", "Tuesday", "Wednesday"]:
        new_assignment = assignment.copy()
        new_assignment[var] = value
        if consistent(new_assignment):
            result = backtrack(new_assignment)
            if result is not None:
                return result
    return None


def select_unassigned_variable(assignment):
    """Chooses a variable not yet assigned, in order."""
    for variable in VARIABLES:
        if variable not in assignment:
            return variable
    return None


def consistent(assignment):
    """Checks to see if an assignment is consistent."""
    for (x, y) in CONSTRAINTS:

        # Only consider arcs where both are assigned
        if x not in assignment or y not in assignment:
            continue

        # If both have same value, then not consistent
        if assignment[x] == assignment[y]:
            return False

    # If nothing inconsistent, then assignment is consistent
    return True


solution = backtrack(dict())
print(solution)

Result

After using the backtracking algorithm we get the result. And we solve the problem as every node is satisfied. There is no duplication or constraint. Result is

Firstly we set some variables and constraints using problem nodes. Then we use the backtracking algorithm and check the assignment is complete or not. Then select the unassigned variable and check the assignment is a constraint or not. Then assign the backtracking in the solution and print the solution and get the result.

>

Conclusion:

Very first, all of us launched the issue. Next, all of us clarify the issue as well as the way you may resolve the issue.

Therefore this is actually the best AI course in Bangladesh.

You are free to copy the code from here.

Thank you all for reading this article.