/Search-Strategies

In this project, I aim to create a package that contains all the basic search strategies employed in Artificial Intelligence and use them for one of the very basic tasks in AI. Pathfinding.

Primary LanguagePython

Search Strategies

Author: Satwik Srivastava

Profiles:

Release: alpha-stable


Version: 0.50


Binder

Description:
In this script I have created all the basic search strategies employed in Artificial Intelligence. These include but are not limited to the following:

  1. Uninformed Search Strategies:
    1. BFS
    2. DFS
    3. Uniform Cost Search
  2. Informed Search Strategies:
    1. A Star Search
  3. Game Search Strategies:
    1. Alpha-Beta Search
  4. Backtracking Search

1. Table Of Contents

2. Introduction

2.1 Uninformed Search

  1. Breadth First Search (BFS)
  2. Depth First Search (DFS)
  3. Uniform Cost Search

2.2 Informed Search

  1. A Star Search

2.3 Game Search

  1. Alpha-Beta Search

All These algorithms are implemented on the tree and the graph data-structures and are used to solve the shortest path problem.

3. Installation and Usage

!NOTE! : Currently I have not packaged this as a module so you have to clone it directly into your working directory.

Just clone or download the SearchStrategies.py file and import it as shown below.

import SearchStrategies as ss
print(ss.__version__)

This should print the current version of the module. If not it is either not downloaded or not placed in your working directory.

4. ChangeLog

4.1 Version 0.50

  • BFS and DFS classes are now fully available and all the methods required are now completed. Some handy functions have been added too.
  • The find function is added to find a value in a Binary Tree.
  • Added create_adjacency_list for trees to convert them into graphs for interoperability.
  • All shortest path methods are now available and return path, cost as there return parameters and across the board a little homogeniety has been introduced.

4.2 Version 0.49

  • Added create_adjacency_list for trees to convert them into graphs for interoperability.
  • Creating a tree can now initialize the keys and the parents (uses initialize_parents and initialize_keys)
  • The DFS class now supports the shortest path calculation for trees.

4.3 Version 0.45

  • Changed the verbose functionality across BFS class to introduce more homogeniety between outputs.
  • DFS Class has been added to the module with the traverse() method for both trees and graphs.
  • NOTE: The traverse method for tree currently does preorder traversal.
  • Fixed some bugs in the implementation of BFS.

4.4 Version 0.40

  • The BFS Class has been added into the module along with relevant supporting data-structures such as Graph and Tree. This class supports methods for traversal of the data structure and to find the shortest path given a source and a target.

4.4 Version 0.38

  • Added Basic Data Structures such as Tree and Graphs and added traversal Methods for the same to the BFS Class.

5. Documentation

5.1 Tree

The Tree Data Structure is a fundamental datastructure for proper and efficient storage and organisation of data.

5.1.1 Binary Tree

Binary Tree
Source: GeeksForGeeks
A binary tree is a data-structure that in which each node has atmost two children. It can be represented as tuple (L, S, R) The binary tree can be created using this module as follows:

import SearchStrategies as ss

root_single = ss.TreeNode(4)
tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

root = ss.create_tree(tree_tuple)

NOTE: Currently Working on Documentation. Please refer to the test.ipynb for an onhande demo.

6. Further Plans

  1. Package the file into a python Module.
  2. Add BSTs to the project.
  3. Add Informed Search Strategies such as Astar search.