Scribd
Upload
5 views4 pages

A* and Best-First Search Algorithms

The document provides implementations of two pathfinding algorithms: A* Search and Recursive Best-First Search. The A* algorithm is designed to find the shortest path in a graph using a heuristic function, while the Recursive Best-First Search algorithm utilizes a priority queue to explore paths based on their costs. Both algorithms are demonstrated with example graphs and output paths.

Uploaded by

yashwhatsapp2004
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views4 pages

A* and Best-First Search Algorithms

The document provides implementations of two pathfinding algorithms: A* Search and Recursive Best-First Search. The A* algorithm is designed to find the shortest path in a graph using a heuristic function, while the Recursive Best-First Search algorithm utilizes a priority queue to explore paths based on their costs. Both algorithms are demonstrated with example graphs and output paths.

Uploaded by

yashwhatsapp2004
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Implement the A* Search algorithm for solving a path

finding problem
Code:
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):


open_lst = set([start])
closed_lst = set([])

poo = {}
poo[start] = 0

par = {}
par[start] = start

while len(open_lst) > 0:


n = None
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 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 (m, weight) in self.get_neighbors(n):

if m not in open_lst and m not in closed_lst:


open_lst.add(m)
par[m] = n
poo[m] = poo[n] + weight

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)

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')

Output:
Path found: ['A', 'B', 'D']

['A', 'B', 'D']


Implement the Recursive Best-First Search algorithm for the
same problem

Code:
from queue import PriorityQueue
v = 14
graph = [[] for i in range(v)]

# Function For Implementing Best First Search


# Gives output path having lowest cost

def best_first_search(actual_Src, target, n):


visited = [False] * n
pq = PriorityQueue()
[Link]((0, actual_Src))
visited[actual_Src] = True

while [Link]() == False:


u = [Link]()[1]
# Displaying the path having lowest cost
print(u, end=" ")
if u == target:
break

for v, c in graph[u]:
if visited[v] == False:
visited[v] = True
[Link]((c, v))
print()

# Function for adding edges to graph

def addedge(x, y, cost):


graph[x].append((y, cost))
graph[y].append((x, cost))

# The nodes shown in above example(by alphabets) are


# implemented using integers addedge(x,y,cost);
addedge(0, 1, 3)
addedge(0, 2, 6)
addedge(0, 3, 5)
addedge(1, 4, 9)
addedge(1, 5, 8)
addedge(2, 6, 12)
addedge(2, 7, 14)
addedge(3, 8, 7)
addedge(8, 9, 5)
addedge(8, 10, 6)
addedge(9, 11, 1)
addedge(9, 12, 10)
addedge(9, 13, 2)

source = 0
target = 9
best_first_search(source, target, v)

Output:
0 1 3 2 8 9

You might also like