libsearch |

Description

A Library of search algorithms, used in State Space Problems where the solution is based on a search into a collection of different states, starting from an Initial state and following specific rules to get from that state to next possible states until a Goal state has been reached.

• Initial State ​ : the state which represents the current description of the problem, from which the search will begin.
• State Space : ​ the set of all possible States
• Actions ​ : a function that takes a State as an argument and return a set of resulting States.
• Goal State(s) ​ : a State or a set of final States defined by specific rules to terminate the search and indicate that an acceptable solution was found.

Implemented Algorithms

The following algorithms are supported.

Blind Search

• Depth First Search
• Breadth First Search
• Iterative Deepening
• Branch and Bound

Heuristic Search

• Best First Search
• A Star
• Iterative Deepening(A- Star)

Getting started

Install the latest version with:

pip install libsearch

Usage

from libsearch import function

Replace function with the algorithm you wish to use by following: In parenthesis you will find the required arguments for each function. (actions is a function as in description above which returns child State(s) from a parent State)

Blind Search Algorithms:

depth_first_search(actions=actions, start=InitialState, goal=GoalState)

breadth_first_search(actions=actions, start=InitialState, goal=GoalState)

iterative_deepening(actions=actions, start=InitialState, goal=GoalState)

For Branch and Bound a path_cost function should be provided which returns the cost of reaching a State.

branch_and_bound(actions=actions, start=InitialState, goal=GoalState, path_cost=path_cost)

Heuristic Search Algorithms:

heuristic: A heuristic function defined be the user unique for each problem which returns an estimated cost to reach GoalState from current State.

best_first_search(actions=actions, start=InitialState, goal=GoalState, heuristic=heuristic)

a_star(actions=actions, start=InitialState, goal=GoalState, heuristic=heuristic)

iterative_deepening_a_star(actions=actions, start=InitialState, goal=GoalState, heuristic=heuristic)

(Optional arguments)

For evaluation purposes the following can be set as arguments alonside the required above to return the number of explored states or/and the states the algorithms explored before reaching the solution.

count_states=True            #if True it will return the number of explored states too. num_explored
show_explored=True           #if True it will return the explored(closed) set too.

Solution

The solution returned by algorithms is a python Set consisting of (list_of_actions, list_of_states).
list_of_actions: the actions it took to reach each State on the path to Goal State
list_of_states: the path to the Goal State from Initial State

Example

Usage of Branch and Bound algorithm for the well-known algorithmic problem Traveling Salesman (TSP).
In the following Complete Weighted Graph figure each city is represented by a letter and each path has a path cost:

We use a Dictionary to implement this Graph in python:

tspGraph = {'A': {'B':8, 'C':5, 'D':10, 'E':8},
        'B': {'A':8, 'C':7, 'D':6, 'E':6},
        'C': {'A':5, 'B':7, 'D':9, 'E':3},
        'D': {'A':10, 'B':6, 'C':9, 'E':4},
        'E': {'A':8, 'B':6, 'C':3, 'D':4}}

In this problem States are cities represented by their letters and actions are moves from a city to another. e.g The action "A-B" applied to State "A" will result to a new State "B" and has a cost(weight) of 8.

In our module we import the branch and bound function:

from libsearch import branch_and_bound

Lets assign the function to a variable (eg. solution):

solution = branch_and_bound(actions=g.fullneighbors, start='A', goal='A', path_cost=g.path_cost)

If we were to print solution we would get the following:

(['A-B', 'A-B-D', 'A-B-D-E', 'A-B-D-E-C', 'A-B-D-E-C-A'], ['B', 'D', 'E', 'C', 'A'])

The first list are the actions (moving from each letter(State) to the next one) and the latter is a list of States representing the path to reach the Goal State "A", whereas in our case it is the same as the Initial State as described in TSP problem.

Optinal arguments

If we wish to see how many states the branch and bound algorithm explored:

solution, num_explored = branch_and_bound(actions=g.fullneighbors, start='A', goal='A', path_cost=g.path_cost, count_states=True)

Checking the value of num_explored we can see that 68 States(path combined) were explored before reaching the Goal.

More details on the implementation of fullneighbors function which return child States for the specific TSP problem and the path_cost function which return the cost assigned to each path, can be found on graph.py in examples folder.

Notes

This implementation of search algorithms as functions can be used virtually in any problem that can be defined as a search in a State Space, as long as the User will define the actions function to generate new State from an existing one and in case of Heuristic Search a heuristic function to estimate the cost of reaching the Goal State.

In examples folder you can experiment with different algorithms on a Maze problem maze.py.