# A* Algorithm – Introduction to The Algorithm (With Python Implementation)

In this article, let’s try to understand the concept of the A* Algorithm and its importance. It is one of the heuristic search algorithms which is primarily used to determine which among the several alternatives will be most efficient to reach a particular goal state.

## What is A* Algorithm?

A*Algorithm (pronounced as A-star) is a combination of ‘branch and bound search algorithm’ and ‘best search algorithm’ combined with the dynamic programming principle. The A* Algorithm is well-known because it is used for locating path and graph traversals. This algorithm is used in numerous online maps and games. It uses a heuristic or evaluation function usually denoted by f(X) to determine the order in which the search visits nodes in the tree. The heuristic function for a node N is defined as follows:

f(N) = g(N)+h(N)

The function g is a measure of the cost of getting from the start node to the current node N, i.e., it is the sum of the costs of the rules that were applied along the best path to the current node. The function h is an estimate of the additional cost of getting from the current node N to the goal node. This is the place where knowledge about the problem domain is exploited. Generally, the A* algorithm is called OR graph/tree search algorithm.

A* algorithm incrementally searches all the routes starting from the start node until it finds the shortest path to a goal. Starting with a given node, the algorithm expands the node with the lowest f(x) value. It maintains a set of partial solutions. Unexpanded leaf nodes of expanded nodes are stored in a queue with corresponding f values. This queue can be maintained as a priority queue.

## Example

Let us consider an example of an eight puzzle again and solve it by using the A* algorithm. The simple evaluation function f(x) is defined as follows:

`f(x) = g(x)+h(X), `

where

• h(X) = the number of tiles not in their goal position in a given state X
• g(X) = depth of node X in the search tree

Given

Let’s try to develop a search tree for this problem by calculating the values of f(x) with the help of g(x) and h(x).

## Implementation in Python

```from copy import deepcopy
import numpy as np
import time

def bestsolution(state):
bestsol = np.array([], int).reshape(-1, 9)
count = len(state) - 1
while count != -1:
bestsol = np.insert(bestsol, 0, state[count]['puzzle'], 0)
count = (state[count]['parent'])
return bestsol.reshape(-1, 3, 3)

# checks for the uniqueness of the iteration(it).
def all(checkarray):
set=[]
for it in set:
for checkarray in it:
return 1
else:
return 0

# number of misplaced tiles
def misplaced_tiles(puzzle,goal):
mscost = np.sum(puzzle != goal) - 1
return mscost if mscost > 0 else 0

def coordinates(puzzle):
pos = np.array(range(9))
for p, q in enumerate(puzzle):
pos[q] = p
return pos

# start of 8 puzzle evaluvation, using Misplaced tiles heuristics
def evaluvate_misplaced(puzzle, goal):
steps = np.array([('up', [0, 1, 2], -3),('down', [6, 7, 8],  3),('left', [0, 3, 6], -1),('right', [2, 5, 8],  1)],
dtype =  [('move',  str, 1),('position', list),('head', int)])

dtstate = [('puzzle',  list),('parent', int),('gn',  int),('hn',  int)]

costg = coordinates(goal)
# initializing the parent, gn and hn, where hn is misplaced_tiles  function call
parent = -1
gn = 0
hn = misplaced_tiles(coordinates(puzzle), costg)
state = np.array([(puzzle, parent, gn, hn)], dtstate)

#priority queues with position as keys and fn as value.
dtpriority = [('position', int),('fn', int)]

priority = np.array([(0, hn)], dtpriority)

while 1:
priority = np.sort(priority, kind='mergesort', order=['fn', 'position'])
position, fn = priority[0]
# sort priority queue using merge sort,the first element is picked for exploring.
priority = np.delete(priority, 0, 0)
puzzle, parent, gn, hn = state[position]
puzzle = np.array(puzzle)

blank = int(np.where(puzzle == 0)[0])

gn = gn + 1
c = 1
start_time = time.time()
for s in steps:
c = c + 1
if blank not in s['position']:
openstates = deepcopy(puzzle)

if ~(np.all(list(state['puzzle']) == openstates, 1)).any():
end_time = time.time()
if (( end_time - start_time ) > 2):
print(" The 8 puzzle is unsolvable \n")
break

hn = misplaced_tiles(coordinates(openstates), costg)
# generate and add new state in the list
q = np.array([(openstates, position, gn, hn)], dtstate)
state = np.append(state, q, 0)
# f(n) is the sum of cost to reach node
fn = gn + hn

q = np.array([(len(state) - 1, fn)], dtpriority)
priority = np.append(priority, q, 0)

if np.array_equal(openstates, goal):
print(' The 8 puzzle is solvable \n')
return state, len(priority)

return state, len(priority)

# initial state
puzzle = []

puzzle.append(2)
puzzle.append(8)
puzzle.append(3)
puzzle.append(1)
puzzle.append(6)
puzzle.append(4)
puzzle.append(7)
puzzle.append(0)
puzzle.append(5)

#goal state
goal = []

goal.append(1)
goal.append(2)
goal.append(3)
goal.append(8)
goal.append(0)
goal.append(4)
goal.append(7)
goal.append(6)
goal.append(5)

state, visited = evaluvate_misplaced(puzzle, goal)
bestpath = bestsolution(state)
print(str(bestpath).replace('[', ' ').replace(']', ''))
totalmoves = len(bestpath) - 1
print('\nSteps to reach goal:',totalmoves)
visit = len(state) - visited
print('Total nodes visited: ',visit, "\n")

```