Artificial Intelligence State Space Search

- Introduction

State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property. [1]

- Searches Covered Here

The following are the searches with their frontiers as:

• Depth First Search (DFS) - Stack/Recursion
• Breadth First Search (BFS) - Queue
• Iterative Deepening Search (IDS) - Stack/Recursion + Queue
• Greedy Best First Search (Greedy) - Priority Queue
• A Star Search (A*) - Priority Queue

- Problem Statement

We are given a 2D grid (N x M dimensions) in which our goal is to reach from source to destination using the minimum (optimal) path.

Example:

For Grid:
0 0 0 0 0 
1 0 1 1 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

Source: (0, 0)
Destination: (4, 4)
Optimal Path Cost: 5
Optimal Path: {(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)}

Each Problem will run with their own time complexity but will give the same output as above for the same configuration

Solution

The solution is for N x M dimensional grid. Algorithms optimize their route to find the shortest path as fast as possible. There are 3 input files given that can be tested, whilst other (your own or you friends) test cases can run aswell.

To create the testcase file, the format is as:

N M
source_x source_y
destination_x destination_y
grid of NxM dimensions

- Animations

• DFS vs BFS Animation

• Iterative Deepening Search Animation

• A Animation*

- References

[1] Wikipedia - State Space Search