https en wikipedia orgwikihillclimbing an interface to define search problems the interface will be illustrated using the example of mathematical function the constructor of the search problem x the x coordinate of the current search state y the y coordinate of the current search state stepsize size of the step to take when looking for neighbors functiontooptimize a function to optimize having the signature fx y returns the output of the function called with current x and y coordinates def testfunctionx y return x y searchproblem0 0 1 testfunction score 0 0 0 0 searchproblem5 7 1 testfunction score 5 7 12 12 returns a list of coordinates of neighbors adjacent to the current coordinates neighbors 0 1 2 3 4 5 6 7 hash the string representation of the current search state check if the 2 objects are equal string representation of the current search state strsearchproblem0 0 1 none x 0 y 0 strsearchproblem2 5 1 none x 2 y 5 implementation of the hill climbling algorithm we start with a given state find all its neighbors move towards the neighbor which provides the maximum or minimum change we keep doing this until we are at a state where we do not have any neighbors which can improve the solution args searchprob the search state at the start findmax if true the algorithm should find the maximum else the minimum maxx minx maxy miny the maximum and minimum bounds of x and y visualization if true a matplotlib graph is displayed maxiter number of times to run the iteration returns a search state having the maximum or minimum score going to direction with greatest ascent to direction with greatest descent we found at least one neighbor which improved the current state since we have no neighbor that improves the solution we stop the search starting the problem with initial coordinates 3 4 starting the problem with initial coordinates 12 47 https en wikipedia org wiki hill_climbing an interface to define search problems the interface will be illustrated using the example of mathematical function the constructor of the search problem x the x coordinate of the current search state y the y coordinate of the current search state step_size size of the step to take when looking for neighbors function_to_optimize a function to optimize having the signature f x y returns the output of the function called with current x and y coordinates def test_function x y return x y searchproblem 0 0 1 test_function score 0 0 0 0 searchproblem 5 7 1 test_function score 5 7 12 12 returns a list of coordinates of neighbors adjacent to the current coordinates neighbors 0 1 2 3 _ 4 5 6 7 hash the string representation of the current search state check if the 2 objects are equal string representation of the current search state str searchproblem 0 0 1 none x 0 y 0 str searchproblem 2 5 1 none x 2 y 5 implementation of the hill climbling algorithm we start with a given state find all its neighbors move towards the neighbor which provides the maximum or minimum change we keep doing this until we are at a state where we do not have any neighbors which can improve the solution args search_prob the search state at the start find_max if true the algorithm should find the maximum else the minimum max_x min_x max_y min_y the maximum and minimum bounds of x and y visualization if true a matplotlib graph is displayed max_iter number of times to run the iteration returns a search state having the maximum or minimum score list to store the current score at each iteration to hold the next best neighbor do not want to visit the same state again neighbor outside our bounds finding max going to direction with greatest ascent finding min to direction with greatest descent we found at least one neighbor which improved the current state since we have no neighbor that improves the solution we stop the search starting the problem with initial coordinates 3 4 starting the problem with initial coordinates 12 47
import math


class SearchProblem:
    

    def __init__(self, x: int, y: int, step_size: int, function_to_optimize):
        
        self.x = x
        self.y = y
        self.step_size = step_size
        self.function = function_to_optimize

    def score(self) -> int:
        
        return self.function(self.x, self.y)

    def get_neighbors(self):
        
        step_size = self.step_size
        return [
            SearchProblem(x, y, step_size, self.function)
            for x, y in (
                (self.x - step_size, self.y - step_size),
                (self.x - step_size, self.y),
                (self.x - step_size, self.y + step_size),
                (self.x, self.y - step_size),
                (self.x, self.y + step_size),
                (self.x + step_size, self.y - step_size),
                (self.x + step_size, self.y),
                (self.x + step_size, self.y + step_size),
            )
        ]

    def __hash__(self):
        
        return hash(str(self))

    def __eq__(self, obj):
        
        if isinstance(obj, SearchProblem):
            return hash(str(self)) == hash(str(obj))
        return False

    def __str__(self):
        
        return f"x: {self.x} y: {self.y}"


def hill_climbing(
    search_prob,
    find_max: bool = True,
    max_x: float = math.inf,
    min_x: float = -math.inf,
    max_y: float = math.inf,
    min_y: float = -math.inf,
    visualization: bool = False,
    max_iter: int = 10000,
) -> SearchProblem:
    
    current_state = search_prob
    scores = []  
    iterations = 0
    solution_found = False
    visited = set()
    while not solution_found and iterations < max_iter:
        visited.add(current_state)
        iterations += 1
        current_score = current_state.score()
        scores.append(current_score)
        neighbors = current_state.get_neighbors()
        max_change = -math.inf
        min_change = math.inf
        next_state = None  
        for neighbor in neighbors:
            if neighbor in visited:
                continue  
            if (
                neighbor.x > max_x
                or neighbor.x < min_x
                or neighbor.y > max_y
                or neighbor.y < min_y
            ):
                continue  
            change = neighbor.score() - current_score
            if find_max:  
                
                if change > max_change and change > 0:
                    max_change = change
                    next_state = neighbor
            else:  
                
                if change < min_change and change < 0:
                    min_change = change
                    next_state = neighbor
        if next_state is not None:
            
            current_state = next_state
        else:
            
            solution_found = True

    if visualization:
        from matplotlib import pyplot as plt

        plt.plot(range(iterations), scores)
        plt.xlabel("Iterations")
        plt.ylabel("Function values")
        plt.show()

    return current_state


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    def test_f1(x, y):
        return (x**2) + (y**2)

    
    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
    local_min = hill_climbing(prob, find_max=False)
    print(
        "The minimum score for f(x, y) = x^2 + y^2 found via hill climbing: "
        f"{local_min.score()}"
    )

    
    prob = SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_f1)
    local_min = hill_climbing(
        prob, find_max=False, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
    )
    print(
        "The minimum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 "
        f"and 50 > y > - 5 found via hill climbing: {local_min.score()}"
    )

    def test_f2(x, y):
        return (3 * x**2) - (6 * y)

    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
    local_min = hill_climbing(prob, find_max=True)
    print(
        "The maximum score for f(x, y) = x^2 + y^2 found via hill climbing: "
        f"{local_min.score()}"
    )