A Star Algorithm
Basic concepts of A*
Where
- g (n) : The actual cost path from the start node to the current node.
- h ( n) : The actual cost path from the current node to goal node.
- f (n) : The actual cost path from the start node to the goal node.
For the implementation of A* algorithm we have to use two arrays namely OPEN and CLOSE.
OPEN:
An array that contains the nodes that have been generated but have not been yet examined till yet.
CLOSE:
An array which contains the nodes which are examined.
Algorithm
1: Firstly, Place the starting node into OPEN and find its f (n) value.
2: Then remove the node from OPEN, having the smallest f (n) value. If it is a goal node, then stop and return to success.
3: Else remove the node from OPEN, and find all its successors.
4: Find the f (n) value of all the successors, place them into OPEN, and place the removed node into CLOSE.
5: Goto Step-2.
6: Exit.
from collections import deque
class Graph:
def __init__(self, adjac_lis):
self.adjac_lis = adjac_lis
def get_neighbors(self, v):
return self.adjac_lis[v]
# This is heuristic function which is having equal values for all nodes
def h(self, n):
H = {
‘A’: 1,
‘B’: 1,
‘C’: 1,
‘D’: 1
}
return H[n]
def a_star_algorithm(self, start, stop):
# In this open_lst is a lisy of nodes which have been visited, but who’s
# neighbours haven’t all been always inspected, It starts off with the start
#node
# And closed_lst is a list of nodes which have been visited
# and who’s neighbors have been always inspected
open_lst = set([start])
closed_lst = set([])
# poo has present distances from start to all other nodes
# the default value is +infinity
poo = {}
poo[start] = 0
# par contains an adjac mapping of all nodes
par = {}
par[start] = start
while len(open_lst) > 0:
n = None
# it will find a node with the lowest value of f() –
for v in open_lst:
if n == None or poo[v] + self.h(v) < poo[n] + self.h(n):
n = v;
if n == None:
print(‘Path does not exist!’)
return None
# if the current node is the stop
# then we start again from start
if n == stop:
reconst_path = []
while par[n] != n:
reconst_path.append(n)
n = par[n]
reconst_path.append(start)
reconst_path.reverse()
print(‘Path found: {}’.format(reconst_path))
return reconst_path
# for all the neighbors of the current node do
for (m, weight) in self.get_neighbors(n):
# if the current node is not presentin both open_lst and closed_lst
# add it to open_lst and note n as it’s par
if m not in open_lst and m not in closed_lst:
open_lst.add(m)
par[m] = n
poo[m] = poo[n] + weight
# otherwise, check if it’s quicker to first visit n, then m
# and if it is, update par data and poo data
# and if the node was in the closed_lst, move it to open_lst
else:
if poo[m] > poo[n] + weight:
poo[m] = poo[n] + weight
par[m] = n
if m in closed_lst:
closed_lst.remove(m)
open_lst.add(m)
# remove n from the open_lst, and add it to closed_lst
# because all of his neighbors were inspected
open_lst.remove(n)
closed_lst.add(n)
print(‘Path does not exist!’)
return None
adjac_lis = {
‘A’: [(‘B’, 1), (‘C’, 3), (‘D’, 7)],
‘B’: [(‘D’, 5)],
‘C’: [(‘D’, 12)]
}
graph1 = Graph(adjac_lis)
graph1.a_star_algorithm(‘A’, ‘D’)