searches.hill_climbing¶
Classes¶
An interface to define search problems. |
Functions¶
|
Implementation of the hill climbling algorithm. |
|
Module Contents¶
- class searches.hill_climbing.SearchProblem(x: int, y: int, step_size: int, function_to_optimize)¶
An interface to define search problems. The interface will be illustrated using the example of mathematical function.
- __eq__(obj)¶
Check if the 2 objects are equal.
- __hash__()¶
hash the string representation of the current search state.
- __str__()¶
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’
- get_neighbors()¶
Returns a list of coordinates of neighbors adjacent to the current coordinates.
Neighbors: | 0 | 1 | 2 | | 3 | _ | 4 | | 5 | 6 | 7 |
- score() int¶
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
- function¶
- step_size¶
- x¶
- y¶
- searches.hill_climbing.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¶
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.
- searches.hill_climbing.test_f1(x, y)¶