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)
openstates[blank], openstates[blank + s['head']] = openstates[blank + s['head']], openstates[blank]
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")
Output:
Admissibility of A*
A search algorithm is admissible if, for any graph, it always terminates in an optimal path from the start state to the goal state if the path exists. We have seen earlier that if the heuristic function ‘h’ underestimates the actual value from the current state to the goal state, then it bounds to give an optimal solution and hence is called an admissible function. So, we can say that A* always terminates with the optimal path in case h is an admissible heuristic function.
Limitations
The precision of the heuristic technique used to calculate h has a significant impact on how speedily the A* search is executed (n). Hence, has issues with complexity.
Summary
In this article, we have learned one of the most optimal algorithms knowns as an A* Algorithm. This search algorithm helps to solve many common path-finding problems like the N-Queen problem, 0-1 Knapsack Problem, Traveling salesman problem, etc. This algorithm is known to solve complex problems, it is also used for network routing protocols. It also helps in defining other algorithms. It has wide applications in the field of artificial intelligence.