# 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’)