15-Puzzle

Comparison of BFS, DFID, A* and IDA* algorithms on the 15-Puzzle Problem.

1. Puzzle Statement

The 15 puzzle is a sliding puzzle having 15 square tiles numbered 1–15 in a 4x4 frame, leaving one unoccupied tile.
Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically.
Given state of the puzzle is known as the initial state. And the ordering of tiles required to achieve is called the final state/goal state.

Example:

2. Algorithms

2.1 Breadth First Search (BFS):

BFS is a method used for traversing a graph. It starts at any item we want to use as a starting position in a graph, and explores all of the neighbour items at the present depth before moving on to the items at the next depth level.

Pseudocode:

Let G be a graph with starting node S and Final node F. Let Q be a queue.

2.2 Defth First Iterative Deepening (DFID):

DFID is a state space or graph search strategy in which a depth-limited version of Depth First Search (DFS) is run repeatedly with increasing depth limits until the goal is found.

Pseudocode:

Let G be a graph with starting node S and Final node F. Let Q be a priority queue of nodes. Let depth allowed be D.

2.3 A*:

A* is a graph traversal and path search algorithm. Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.

Pseudocode:

Let G be a graph with starting node S and Final node F. Let Q be a priority queue of nodes. Let h(S) be the heuristic value (f(n) = g(n) + h(n)) of S, g(S) = 0.

2.4 Iterative Deepening A* (IDA*):

IDA* is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of DFID search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm

Pseudocode:

Let G be a graph with starting node S and Final node F. Let Q be a priority queue of nodes. Let h(S) be the heuristic value (f(n) = g(n) + h(n)) of S, g(S) = 0. Suppose B be the initial bound on heuristic.

3. Properties of Algorithms

Let G be a graph having starting node S and goal node G. Let the average branching factor be ‘b’ and the depth of G from S be ‘d’.

3.1 Breadth First Search (BFS):

Time Complexity, T(n) = O(b^d)
Space Complexity, S(n) = O(b^d)
Completeness : Yes
Optimality : Yes

3.2 Defth First Iterative Deepening (DFID):

Time Complexity, T(n) = O(b^d)
Space Complexity, S(n) = O(bd)
Completeness : Yes
Optimality : Yes

3.3 A*:

Time Complexity, T(n) = O(b^d)
Space Complexity, S(n) = O(b^d)
Completeness : Yes
Optimality : Yes

3.4 Iterative Deepening A* (IDA*):

Time Complexity, T(n) = O(b^d)
Space Complexity, S(n) = O(bd)
Completeness : Yes
Optimality : Yes