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]
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
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 - DFS vs BFS Animation
- Iterative Deepening Search Animation
- A Animation*
