Untitled

import random
import time

class CSP:
    def __init__(self, variables, domains, constraints, cost_functions):
        self.variables = variables
        self.domains = domains
        self.constraints = constraints
        self.cost_functions = cost_functions

def dfs_solver_with_cost(csp):
    def dfs_helper(assignment):
        if len(assignment) == len(csp.variables):
            return assignment
        
        unassigned = [v for v in csp.variables if v not in assignment]
        var = min(unassigned, key=lambda v: min(calculate_cost(v, val) for val in csp.domains[v]))
        
        sorted_domain = sorted(csp.domains[var], key=lambda val: calculate_cost(var, val))
        
        for value in sorted_domain:
            if consistent(var, value, assignment, csp.constraints):
                assignment[var] = value
                result = dfs_helper(assignment)
                if result is not None:
                    return result
                del assignment[var]
        return None

    def consistent(var, value, assignment, constraints):
        for constraint in constraints:
            if var in constraint.scope:
                if not constraint.satisfied(assignment | {var: value}):
                    return False
        return True

    def calculate_cost(var, val):
        return sum(cost_function(val) for cost_function in csp.cost_functions.get(var, []))

    return dfs_helper({})

def dfs_solver(csp):
    def dfs_helper(assignment):
        if len(assignment) == len(csp.variables):
            return assignment
        
        var = random.choice([v for v in csp.variables if v not in assignment])
        for value in csp.domains[var]:
            if consistent(var, value, assignment, csp.constraints):
                assignment[var] = value
                result = dfs_helper(assignment)
                if result is not None:
                    return result
                del assignment[var]
        return None

    def consistent(var, value, assignment, constraints):
        for constraint in constraints:
            if var in constraint.scope:
                if not constraint.satisfied(assignment | {var: value}):
                    return False
        return True

    return dfs_helper({})

def compare_dfs_performance(csp, num_runs=5):
    total_time_original = 0
    total_time_with_cost = 0
    
    for _ in range(num_runs):
        start = time.time()
        dfs_solver(csp)
        end = time.time()
        total_time_original += (end - start)
        
        start = time.time()
        dfs_solver_with_cost(csp)
        end = time.time()
        total_time_with_cost += (end - start)
    
    avg_time_original = total_time_original / num_runs
    avg_time_with_cost = total_time_with_cost / num_runs
    
    print(f"Average time for original DFS: {avg_time_original:.6f} seconds")
    print(f"Average time for DFS with cost: {avg_time_with_cost:.6f} seconds")
    print(f"Speedup factor: {avg_time_original / avg_time_with_cost:.2f}")

def run_empirical_comparison():
    for n in range(3, 8, 2):  # Test for problem sizes 3, 5, 7
        print(f"\nTesting for problem size n = {n}")
        
        variables = [f"var_{i}" for i in range(n)]
        domains = {var: list(range(5)) for var in variables}  # Domain of 0-4 for each variable
        constraints = []
        cost_functions = {var: [lambda x: x] for var in variables}  # Simple cost function: f(x) = x
        
        csp = CSP(variables, domains, constraints, cost_functions)
        
        compare_dfs_performance(csp)

# Run the empirical comparison
run_empirical_comparison()