A collection of state space search algorithms.
Project description
Polysearch
This library provides a collection of state space search algorithms designed to solve problems defined by the StateSpaceProblem
interface. The library includes both blind and informed search algorithms, making it versatile for various problem-solving scenarios.
Installation
You can install this software using pip:
pip install -U polysearch
You can install the latest version of the code directly from GitHub:
pip install -U git+https://github.com/chaseburton/polysearch@main
Important Links
- Source code: https://github.com/chaseburton/polysearch
- Documentation: http://polysearch.readthedocs.org
Structure
The library is structured as a package containing several search algorithms. Each algorithm utilizes a standard interface, allowing users to easily switch between algorithms when solving a problem. To demonstrate the usage of these algorithms, three example problems are provided, which can be run using blind_search.py
and informed_search.py
.
Algorithms
The library includes the following algorithms:
- A Star Search (A*)
- Best-First Search (BestFS)
- Branch And Bound (B&B)
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Hill Climbing (HC)
- Iterative Deepening (ID)
- Uniform Cost Search (UCS)
Usage
To use the library, first, create a class for your problem that inherits from the StateSpaceProblem
interface. This interface requires you to define the following methods:
initial_state()
: Returns the initial state of the problem.goal_check(state)
: Checks if the given state is a goal state. Allows for problems with multiple or unknown goal states.operators()
: Returns the list of operators applicable to the problem.apply_operator(operator, state)
: Applies the given operator to the state and returns the resulting state.cost(state1, state2)
: Returns the cost of transitioning from state1 to state2.
After defining your problem, you can use any of the algorithms from the library by importing the desired algorithm and passing your problem instance to it. If needed, you can also provide a heuristic function for informed search algorithms like Best-First Search and A* Search.
Example
# algorithms
from polysearch.algorithms import *
from polysearch.algorithms import a_star_search
from polysearch.algorithms import best_first_search
from polysearch.algorithms import branch_and_bound_search
from polysearch.algorithms import breadth_first_search
from polysearch.algorithms import depth_first_search
from polysearch.algorithms import hill_climbing_search
from polysearch.algorithms import iterative_deepening_search
from polysearch.algorithms import uniform_cost_search
# existing problems
from polysearch.problems import *
from polysearch.problems.maze import MazeProblem
from polysearch.problems.missionaries_and_cannibals import MissionariesAndCannibalsProblem
from polysearch.problems.n_queens import NQueensProblem
# example problem
from your_problem import YourProblem
problem = YourProblem()
solution = a_star_search(problem, heuristic=your_heuristic_function)
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for polysearch-0.0.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 35de91ca9a336fdb19c1f9c49e237ea8ac731bdac7318971e06645f9cc401c55 |
|
MD5 | c6163ed63c4e0e9d8c28772fa1737396 |
|
BLAKE2b-256 | f25829ab98f8a760f672127deafb04cc8450dd2ac4b68af84bb917ec80f8e8d2 |