# Simulated Annealing - Optimization Heuristic
# Description: Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

import random
import math

def simulated_annealing(
    initial_state, 
    evaluate, 
    neighbor, 
    temperature=1000, 
    cooling_rate=0.995, 
    min_temp=0.1, 
    max_iterations=1000
):
    """
    Simulated Annealing: An optimization algorithm inspired by metallurgy.

    This algorithm explores a search space by probabilistically accepting 
    worse solutions to escape local optima, with decreasing probability 
    as the "temperature" cools down.

    Args:
        initial_state (any): Starting point in the search space.
        evaluate (function): Measures the quality of a state (cost function).
            Lower cost is considered better.
        neighbor (function): Generates a nearby alternative state.
        temperature (float): Initial exploration intensity.
        cooling_rate (float): Rate of reducing exploration probability.
        min_temp (float): Stopping temperature threshold.
        max_iterations (int): Limit on total iterations to prevent infinite loops.

    Returns:
        tuple: (best_state, best_cost) found during the search.

    Key Characteristics:
    - Probabilistically accepts worse solutions early on
    - Becomes more selective as temperature decreases
    - Helps escape local optima in complex search spaces

    Time Complexity: O(max_iterations)
    Space Complexity: O(1)
    """
    # Initialize the current state and its evaluation
    current_state = initial_state
    best_state = current_state
    current_cost = evaluate(current_state)
    best_cost = current_cost

    # Track iterations to prevent potential infinite loops
    iterations = 0

    # Simulated annealing main loop
    while temperature > min_temp and iterations < max_iterations:
        # Generate a neighboring state
        candidate_state = neighbor(current_state)
        candidate_cost = evaluate(candidate_state)

        # Calculate the cost difference
        cost_delta = candidate_cost - current_cost

        # Determine if we should accept the new state
        # Accept better states unconditionally
        # Accept worse states with decreasing probability
        if (cost_delta < 0 or 
            random.random() < math.exp(-cost_delta / temperature)):
            current_state = candidate_state
            current_cost = candidate_cost

            # Update the best state if needed
            if current_cost < best_cost:
                best_state = current_state
                best_cost = current_cost

        # Cool down the temperature
        temperature *= cooling_rate
        iterations += 1

    return best_state, best_cost

# Helpful example of how to use the algorithm
def example_usage():
    """
    Example demonstrating simulated annealing for finding 
    a near-optimal solution in a simple problem space.
    """
    def target_sum_evaluate(state):
        """Evaluate how close the sum is to a target value."""
        target = 15
        return abs(sum(state) - target)

    def neighbor_generator(state):
        """Generate a neighboring state by slightly modifying one element."""
        new_state = state.copy()
        index = random.randint(0, len(state) - 1)
        new_state[index] += random.randint(-2, 2)
        return new_state

    # Initial random state
    initial_state = [random.randint(1, 5) for _ in range(3)]

    # Run simulated annealing
    best_solution, best_cost = simulated_annealing(
        initial_state, 
        target_sum_evaluate, 
        neighbor_generator
    )

    print(f"Best Solution: {best_solution}")
    print(f"Best Cost: {best_cost}")