Search module

We already saw how to define a problem. Let's talk about solving them. There are many algorithms that can find the optimal solution to any problem but unfortunately all of them do so in exponential time in the worst case (the worst case being an unsolvable problem). Fortunately, for some practical uses these algorithms can do some pretty good job on finding the solution.

Adder implements many such algorithms. We can separate them in several categories:

Category	Description
Optimal	Optimal algorithms are those that always find the best solution to the problem but at the cost of higher run time.
Suboptimal	Suboptimal algorithms find solution that may not be the best (or the solution may only be approximate) but gets the job done. This allows them to run faster (often nondeterministically).
Uninformed	Uninformed algorithms know nothing about the problem they are solving. They are general and require less information to work but are slower than their informed counterparts.
Informed	Informed algorithms take an additional parameter besides the problem they are solving. The parameter is a function called a heuristic which guides the search.

Optimal uninformed

The best optimal uninformed algorithm currently implemented is known as Iterative Deepening Depth-first Search (IDDFS). The algorithm accepts the problem as parameter and returns either the best solution, problem.FAILURE if no solution exists or problem.SOLUTION_UNKNOWN if it cut the search earlier (see below). Here's how to use it:

import adder.search as search 

problem = MyProblemClass()
solution = search.iterative_deepening_dfs(problem)

IDDFS works by going deeper and deeper into the search space of your problem. This can easily cause him to get stuck if the search space is infinite or just really deep. To handle this (or if you only care about solutions with a certain length), you can pass a secondary argument to IDDFS so that it can cut its search earlier:

solution = search.iterative_deepening_dfs(problem, 10) # Will only search up to depth 10

Optimal informed

In this category resides one of the most popular algorithms (especially in game development) known as A* (read A Star). A* takes your problem and the aforementioned heuristic that guides its search as arguments. It returns either the best solution or problem.FAILURE if no solution exists.

The heuristic is a special function that takes as input a state of the problem and returns an estimation of length of the solution from the given state to the goal state. For example, if you are searching for the shortest path from NYC to LA, then one possible heuristic might be the straight-line distance between each city and LA. One important thing to note is that the heuristic must be admissible which means that the heuristic never overestimates the correct distance. The straight-line distance above is one such heuristic.

Here's how to use A* in Adder:

import adder.search as search 

problem = DistanceProblem("NYC", "LA")
def heuristic(city):
     return distance_between(city, "LA")
solution = search.astar(problem, heuristic)

Suboptimal uninformed

The next two algorithms are known as Hill-Climbing and Random-Restart Search. Hill-Climbing finds local maxima, while Random-Restart runs Hill-Climbing many times until eventually that local maxima produced matches the goal. In that sense, Random-Restart can be considered optimal but most of the time, you'll have Random-Restart cut its search halfway through and return whatever it has found.

import adder.search as search 

problem = MyAwesomeProblem()
local_maxima = search.hill_climbing(problem) 
solution = search.random_restart(problem, 100) # Run 100 restarts (you can also use random_restart(problem) which defaults the iteration count to infinity)

Both functions accept additional parameters but most users won't need them so I won't go in details

Suboptimal informed

My favourite algorithm resides here - Simulated Annealing (SA). SA works in a very interesting way which I won't describe but it is a good example of how computer sciences borrow ideas from many different fields. Anyhow, simulated annealing takes an heuristic just like A*:

import adder.search as search 

problem = MyProblemClass()
def heuristic(state):
    return distance_to(state, problem.goal)

solution = search.simulated_annealing(problem, heuristic)

Simulated annealing takes 3 other arguments that can be used to tweak its behaviour but as in the case of Random-Restart, I won't describe them.