                            PRACTICAL NO:5
                      A * SEARCH ALGORITHM
The A* algorithm is a highly effective and well-known search technique utilized for finding the most efficient path between two points in a graph. It is applied in scenarios such as pathfinding in video games, network routing and various artificial intelligence (Al) applications. It was developed in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael as an improvement on Dijkstra's algorithm.
While Dijkstra's algorithm explores all possible directions around the starting node uniformly
A* combines actual travel cost with an estimated future cost(heuristics)
This optimizes the search process, reduces computational load and ensures the most efficient path is found with minimal unnecessary exploration.
MAP:
CODE:
from queue import PriorityQueue
# Undirected representation of the Romania Map
GRAPH = {
    'oradea': {'zerind': 71, 'sibiu': 151},
    'zerind': {'oradea': 71, 'arad': 75},
    'arad': {'zerind': 75, 'timisoara': 118, 'sibiu': 140},
    'timisoara': {'arad': 118, 'lugoj': 111},
    'lugoj': {'timisoara': 111, 'mehadia': 70},
    'mehadia': {'lugoj': 70, 'drobeta': 75},
    'drobeta': {'mehadia': 75, 'craiova': 120},
    'craiova': {'drobeta': 120, 'rimnicu': 146, 'pitesti': 138},
    'rimnicu': {'craiova': 146, 'sibiu': 80, 'pitesti': 97},
    'sibiu': {'oradea': 151, 'arad': 140, 'fagaras': 99, 'rimnicu': 80},
    'fagaras': {'sibiu': 99, 'bucharest': 211},
    'bucharest': {'fagaras': 211, 'pitesti': 101, 'giurgiu': 90, 'urziceni': 85},
    'giurgiu': {'bucharest': 90},
    'pitesti': {'craiova': 138, 'rimnicu': 97, 'bucharest': 101},
    'urziceni': {'bucharest': 85, 'vaslui': 142, 'hirsova': 98},
    'hirsova': {'urziceni': 98, 'eforie': 86},
    'eforie': {'hirsova': 86},
    'vaslui': {'urziceni': 142, 'iasi': 92},
    'iasi': {'vaslui': 92, 'neamt': 87},
    'neamt': {'iasi': 87}
}
straight_line = {
    'arad': 366, 'zerind': 374, 'oradea': 380, 'sibiu': 253,
    'timisoara': 329, 'lugoj': 244, 'mehadia': 241, 'drobeta': 242,
    'craiova': 160, 'rimnicu': 193, 'fagaras': 176, 'pitesti': 100,
    'bucharest': 0, 'giurgiu': 77, 'urziceni': 80, 'hirsova': 151,
    'eforie': 161, 'vaslui': 199, 'iasi': 226, 'neamt': 234
}
def a_star(source, destination):
    priority_queue = PriorityQueue()
    visited = {}
    # f(n) = g(n) + h(n)
    initial_f = straight_line[source]
    priority_queue.put((initial_f, 0, source, [source]))
    visited[source] = initial_f
    while not priority_queue.empty():
        (f_score, cost, vertex, path) = priority_queue.get()
        if vertex == destination:
            return f_score, cost, path
        for next_node, edge_cost in GRAPH[vertex].items():
            current_cost = cost + edge_cost
            heuristic = current_cost + straight_line[next_node]
            if next_node not in visited or visited[next_node] > heuristic:
                visited[next_node] = heuristic
                priority_queue.put((heuristic, current_cost, next_node, path + [next_node]))
    return None, None, None
def main():
    source = input('ENTER SOURCE: ').strip().lower()
    goal = input('ENTER GOAL: ').strip().lower()
    if source not in GRAPH or goal not in GRAPH:
        print('ERROR: CITY DOES NOT EXIST.')
    else:
        f_score, cost, cheapest_path = a_star(source, goal)
        if cheapest_path:
            print('\nCHEAPEST PATH:')
            print('Estimated Total Cost f(n):', f_score)
            print('Path Cost g(n):', cost)
            print(' -> '.join(cheapest_path))
        else:
            print('No path found.')
if __name__ == '__main__':
    main()
OUTPUT: