Untitled

import random
import time
import matplotlib.pyplot as plt

class Constraint:
    def __init__(self, scope, condition):
        self.scope = scope
        self.condition = condition

    def satisfied(self, assignment):
        return self.condition(*[assignment.get(var) for var in self.scope])

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):
        assignment = assignment.copy()
        assignment[var] = value
        return all(constraint.satisfied(assignment) for constraint in constraints if var in constraint.scope)

    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):
        assignment = assignment.copy()
        assignment[var] = value
        return all(constraint.satisfied(assignment) for constraint in constraints if var in constraint.scope)

    return dfs_helper({})

def compare_dfs_performance(csp, num_runs=10):
    total_time_original = 0
    total_time_with_cost = 0
    original_successes = 0
    cost_successes = 0
    
    for _ in range(num_runs):
        start = time.time()
        result = dfs_solver(csp)
        end = time.time()
        if result is not None:
            total_time_original += (end - start)
            original_successes += 1
        
        start = time.time()
        result = dfs_solver_with_cost(csp)
        end = time.time()
        if result is not None:
            total_time_with_cost += (end - start)
            cost_successes += 1
    
    avg_time_original = total_time_original / original_successes if original_successes > 0 else float('inf')
    avg_time_with_cost = total_time_with_cost / cost_successes if cost_successes > 0 else float('inf')
    
    print(f"Original DFS: {original_successes}/{num_runs} successful runs")
    print(f"DFS with cost: {cost_successes}/{num_runs} successful 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")
    
    if avg_time_original != float('inf') and avg_time_with_cost != float('inf'):
        speedup = avg_time_original / avg_time_with_cost
        print(f"Speedup factor: {speedup:.2f}")
    else:
        print("Speedup factor: N/A (one or both methods failed to find solutions)")
    
    return avg_time_original, avg_time_with_cost

def run_empirical_comparison():
    problem_sizes = list(range(10, 31, 5))  # Test for problem sizes 10, 15, 20, 25, 30
    original_times = []
    cost_times = []
    
    for n in problem_sizes:
        print(f"\nTesting for problem size n = {n}")
        
        variables = [f"var_{i}" for i in range(n)]
        domains = {var: list(range(10)) for var in variables}  # Domain of 0-9 for each variable
        
        # Add some constraints
        constraints = []
        for i in range(n-1):
            constraints.append(Constraint([f"var_{i}", f"var_{i+1}"], lambda x, y: abs(x - y) > 2))
        
        # Add a global constraint
        constraints.append(Constraint(variables, lambda *args: sum(args) % 5 == 0))
        
        # Cost functions: prefer smaller values for odd-indexed variables and larger values for even-indexed variables
        cost_functions = {
            f"var_{i}": [lambda x, i=i: x if i % 2 == 0 else 9-x] for i in range(n)
        }
        
        csp = CSP(variables, domains, constraints, cost_functions)
        
        avg_time_original, avg_time_with_cost = compare_dfs_performance(csp)
        original_times.append(avg_time_original)
        cost_times.append(avg_time_with_cost)
    
    # Plotting the results
    plt.figure(figsize=(10, 6))
    plt.plot(problem_sizes, original_times, marker='o', label='Original DFS')
    plt.plot(problem_sizes, cost_times, marker='s', label='DFS with Cost')
    plt.xlabel('Problem Size (n)')
    plt.ylabel('Average Time (seconds)')
    plt.title('DFS Performance Comparison')
    plt.legend()
    plt.grid(True)
    plt.savefig('dfs_performance_comparison.png')
    plt.show()

# Run the empirical comparison
run_empirical_comparison()