heuristics

def greedy_coin_change(coins, target): """ Greedy algorithm to find the minimum number of coins for a given target. Args: - coins (list): List of available coin denominations. - target (int): The target value to reach using the coins. Returns: - list: A list of coins that sum up to the target, or a message if it's impossible. Example: >>> coins = [1, 5, 10, 25] >>> target = 63 >>> greedy_coin_change(coins, target) [25, 25, 10, 1, 1, 1] """ coins.sort(reverse=True) # Sort coins in descending order for greedy choice result = [] for coin in coins: while target >= coin: target -= coin result.append(coin) return result if target == 0 else "Not possible" # Example usage: coins = [1, 5, 10, 25] target = 63 print(greedy_coin_change(coins, target)) # Output: [25, 25, 10, 1, 1, 1] import random def fitness_function(solution): """ Simple fitness function for a binary solution. Args: - solution (list): A list of binary values representing a solution. Returns: - int: The fitness value, calculated as the sum of the elements (e.g., how many 1's are in the solution). Example: >>> fitness_function([1, 1, 0, 1]) 3 """ return sum(solution) # Count how many 1's in the solution def mutate(solution): """ Randomly mutate a solution by flipping one bit (0 to 1 or 1 to 0). Args: - solution (list): The solution to mutate. Returns: - list: The mutated solution. Example: >>> mutate([1, 0, 1]) [1, 1, 1] """ idx = random.randint(0, len(solution) - 1) solution[idx] = random.randint(0, 1) # Flip a random bit return solution def crossover(parent1, parent2): """ Perform crossover between two parents to generate two children. Args: - parent1 (list): The first parent solution. - parent2 (list): The second parent solution. Returns: - tuple: Two children produced by crossover. Example: >>> crossover([1, 0, 1], [0, 1, 0]) ([1, 0, 0], [0, 1, 1]) """ point = random.randint(1, len(parent1) - 1) child1 = parent1[:point] + parent2[point:] child2 = parent2[:point] + parent1[point:] return child1, child2 def genetic_algorithm(pop_size, num_gen, mutation_rate): """ Basic Genetic Algorithm for optimization problems. Args: - pop_size (int): Population size. - num_gen (int): Number of generations to run the algorithm. - mutation_rate (float): Probability of mutation for each generation. Returns: - list: The best solution found by the algorithm. Example: >>> genetic_algorithm(50, 100, 0.1) [1, 1, 1, 0, 1, 1, 0, 1, 1] """ population = [[random.randint(0, 1) for _ in range(10)] for _ in range(pop_size)] # Initialize random population for gen in range(num_gen): population.sort(key=lambda x: fitness_function(x), reverse=True) # Sort by fitness (descending) next_generation = population[:2] # Keep the top 2 best solutions while len(next_generation) < pop_size: parent1, parent2 = random.sample(population[:10], 2) # Select parents from top 10 child1, child2 = crossover(parent1, parent2) next_generation.append(child1) next_generation.append(child2) population = next_generation # Mutate with a certain probability if random.random() < mutation_rate: population[random.randint(0, pop_size - 1)] = mutate(population[random.randint(0, pop_size - 1)]) return max(population, key=lambda x: fitness_function(x)) # Example usage: best_solution = genetic_algorithm(pop_size=50, num_gen=100, mutation_rate=0.1) print("Best solution:", best_solution, "Fitness:", fitness_function(best_solution)) import heapq def a_star(start, goal, grid): """ A* algorithm to find the shortest path in a 2D grid. Args: - start (tuple): Starting position (row, col). - goal (tuple): Goal position (row, col). - grid (list of list): A 2D grid with 0 as open cells and 1 as obstacles. Returns: - list: The path from start to goal, or "No path found" if no path exists. Example: >>> grid = [ >>> [0, 0, 0, 0], >>> [0, 1, 1, 0], >>> [0, 0, 0, 0], >>> [0, 1, 0, 0] >>> ] >>> start = (0, 0) >>> goal = (3, 3) >>> a_star(start, goal, grid) [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)] """ def heuristic(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) # Manhattan distance open_set = [] heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start)) came_from = {} g_score = {start: 0} f_score = {start: heuristic(start, goal)} while open_set: _, current_cost, current = heapq.heappop(open_set) if current == goal: path = [] while current in came_from:

Mar 23, 2025 - 13:03



def greedy_coin_change(coins, target):
    """
    Greedy algorithm to find the minimum number of coins for a given target.

    Args:
    - coins (list): List of available coin denominations.
    - target (int): The target value to reach using the coins.

    Returns:
    - list: A list of coins that sum up to the target, or a message if it's impossible.

    Example:
    >>> coins = [1, 5, 10, 25]
    >>> target = 63
    >>> greedy_coin_change(coins, target)
    [25, 25, 10, 1, 1, 1]
    """
    coins.sort(reverse=True)  # Sort coins in descending order for greedy choice
    result = []

    for coin in coins:
        while target >= coin:
            target -= coin
            result.append(coin)

    return result if target == 0 else "Not possible"

# Example usage:
coins = [1, 5, 10, 25]
target = 63
print(greedy_coin_change(coins, target))  # Output: [25, 25, 10, 1, 1, 1]





import random

def fitness_function(solution):
    """
    Simple fitness function for a binary solution.

    Args:
    - solution (list): A list of binary values representing a solution.

    Returns:
    - int: The fitness value, calculated as the sum of the elements (e.g., how many 1's are in the solution).

    Example:
    >>> fitness_function([1, 1, 0, 1])
    3
    """
    return sum(solution)  # Count how many 1's in the solution

def mutate(solution):
    """
    Randomly mutate a solution by flipping one bit (0 to 1 or 1 to 0).

    Args:
    - solution (list): The solution to mutate.

    Returns:
    - list: The mutated solution.

    Example:
    >>> mutate([1, 0, 1])
    [1, 1, 1]
    """
    idx = random.randint(0, len(solution) - 1)
    solution[idx] = random.randint(0, 1)  # Flip a random bit
    return solution

def crossover(parent1, parent2):
    """
    Perform crossover between two parents to generate two children.

    Args:
    - parent1 (list): The first parent solution.
    - parent2 (list): The second parent solution.

    Returns:
    - tuple: Two children produced by crossover.

    Example:
    >>> crossover([1, 0, 1], [0, 1, 0])
    ([1, 0, 0], [0, 1, 1])
    """
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

def genetic_algorithm(pop_size, num_gen, mutation_rate):
    """
    Basic Genetic Algorithm for optimization problems.

    Args:
    - pop_size (int): Population size.
    - num_gen (int): Number of generations to run the algorithm.
    - mutation_rate (float): Probability of mutation for each generation.

    Returns:
    - list: The best solution found by the algorithm.

    Example:
    >>> genetic_algorithm(50, 100, 0.1)
    [1, 1, 1, 0, 1, 1, 0, 1, 1]
    """
    population = [[random.randint(0, 1) for _ in range(10)] for _ in range(pop_size)]  # Initialize random population
    for gen in range(num_gen):
        population.sort(key=lambda x: fitness_function(x), reverse=True)  # Sort by fitness (descending)
        next_generation = population[:2]  # Keep the top 2 best solutions
        while len(next_generation) < pop_size:
            parent1, parent2 = random.sample(population[:10], 2)  # Select parents from top 10
            child1, child2 = crossover(parent1, parent2)
            next_generation.append(child1)
            next_generation.append(child2)
        population = next_generation

        # Mutate with a certain probability
        if random.random() < mutation_rate:
            population[random.randint(0, pop_size - 1)] = mutate(population[random.randint(0, pop_size - 1)])

    return max(population, key=lambda x: fitness_function(x))

# Example usage:
best_solution = genetic_algorithm(pop_size=50, num_gen=100, mutation_rate=0.1)
print("Best solution:", best_solution, "Fitness:", fitness_function(best_solution))












import heapq

def a_star(start, goal, grid):
    """
    A* algorithm to find the shortest path in a 2D grid.

    Args:
    - start (tuple): Starting position (row, col).
    - goal (tuple): Goal position (row, col).
    - grid (list of list): A 2D grid with 0 as open cells and 1 as obstacles.

    Returns:
    - list: The path from start to goal, or "No path found" if no path exists.

    Example:
    >>> grid = [
    >>>     [0, 0, 0, 0],
    >>>     [0, 1, 1, 0],
    >>>     [0, 0, 0, 0],
    >>>     [0, 1, 0, 0]
    >>> ]
    >>> start = (0, 0)
    >>> goal = (3, 3)
    >>> a_star(start, goal, grid)
    [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
    """
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan distance

    open_set = []
    heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        _, current_cost, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]  # Return reversed path

        for neighbor in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            neighbor_cell = (current[0] + neighbor[0], current[1] + neighbor[1])
            if 0 <= neighbor_cell[0] < len(grid) and 0 <= neighbor_cell[1] < len(grid[0]) and grid[neighbor_cell[0]][neighbor_cell[1]] != 1:
                tentative_g_score = current_cost + 1  # Assume cost to neighbor is 1
                if neighbor_cell not in g_score or tentative_g_score < g_score[neighbor_cell]:
                    came_from[neighbor_cell] = current
                    g_score[neighbor_cell] = tentative_g_score
                    f_score[neighbor_cell] = tentative_g_score + heuristic(neighbor_cell, goal)
                    heapq.heappush(open_set, (f_score[neighbor_cell], tentative_g_score, neighbor_cell))

    return "No path found"

# Example usage:
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 0, 0]
]
start = (0, 0)
goal = (3, 3)
print(a_star(start, goal, grid))  # Output: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]