Ex.
No:2(a)
Implementation of Informed search algorithms (A*, memory-bounded A*)
Date:
AIM
To implement the A* Search algorithm to find the optimal path between a start node and
a goal node in a weighted graph using heuristic values.
ALGORITHM
1. Initialize the open set with the start node and an empty closed set.
2. Set the g-score of the start node to 0 and assign itself as its parent.
3. While the open set is not empty:
a. Select the node `n` from the open set with the lowest f(n) = g(n) + h(n).
b. If `n` is the goal node, reconstruct the path and terminate.
c. Move `n` from open set to closed set.
d. For each neighbor `m` of `n`:
- If `m` is not in open or closed set, add it to open set and update g-score and parent.
- Else if a shorter path to `m` is found, update g-score and parent.
4. If the goal node is never reached, return that no path exists.
PROGRAM
def aStarAlgo(start_node, stop_node):
open_set = set([start_node])
closed_set = set()
g = {}
parents = {}
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
for v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n=v
if n == stop_node:
path = []
while parents[n] != n:
[Link](n)
n = parents[n]
[Link](start_node)
[Link]()
print("Path found:", path)
return path
for (m, weight) in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
open_set.remove(n)
closed_set.add(n)
print("Path does not exist!")
return None
def get_neighbors(v):
return Graph_nodes.get(v, [])
def heuristic(n):
H_dist = {
'A': 10, 'B': 8, 'C': 5, 'D': 7,
'E': 3, 'F': 6, 'G': 5, 'H': 3,
'I': 1, 'J': 0
}
return H_dist[n]
Graph_nodes = {
'A': [('B', 6), ('F', 3)],
'B': [('C', 3), ('D', 2)],
'C': [('D', 1), ('E', 5)],
'D': [('C', 1), ('E', 8)],
'E': [('I', 5), ('J', 5)],
'F': [('G', 1), ('H', 7)],
'G': [('I', 3)],
'H': [('I', 2)],
'I': [('E', 5), ('J', 3)],
}
aStarAlgo('A', 'J')
OUTPUT
Path found: ['A', 'F', 'G', 'I', 'J']
RESULT
Thus, the A* Search algorithm was successfully implemented, and the optimal path from
node A to J was obtained.