Scribd Logo
Upload

Welcome to Scribd!

  • 14 views

    Ai PRA4

    Uploaded by

    Joshi Labhesh
    The A* algorithm finds the shortest path between two points in a weighted graph by using a priority queue to efficiently explore nodes. It uses the cost of reaching a node ("g" cost) plus a heuristic estimate of reaching the goal ("h" cost) to prioritize nodes. The algorithm guarantees finding the shortest path if the heuristic is admissible and the graph has no negative cycles. Pseudocode and Python code are provided to implement the A* algorithm to find the shortest path between nodes in a sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Ai PRA4

    Uploaded by

    Joshi Labhesh
    14 views4 pages
    The A* algorithm finds the shortest path between two points in a weighted graph by using a priority queue to efficiently explore nodes. It uses the cost of reaching a node ("g" cost) plus a heuristic estimate of reaching the goal ("h" cost) to prioritize nodes. The algorithm guarantees finding the shortest path if the heuristic is admissible and the graph has no negative cycles. Pseudocode and Python code are provided to implement the A* algorithm to find the shortest path between nodes in a sample graph.

    Original Title

    Ai-PRA4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The A* algorithm finds the shortest path between two points in a weighted graph by using a priority queue to efficiently explore nodes. It uses the cost of reaching a node ("g" cost) plus a heuristic estimate of reaching the goal ("h" cost) to prioritize nodes. The algorithm guarantees finding the shortest path if the heuristic is admissible and the graph has no negative cycles. Pseudocode and Python code are provided to implement the A* algorithm to find the shortest path between nodes in a sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    14 views4 pages

    Ai PRA4

    Uploaded by

    Joshi Labhesh
    The A* algorithm finds the shortest path between two points in a weighted graph by using a priority queue to efficiently explore nodes. It uses the cost of reaching a node ("g" cost) plus a heuristic estimate of reaching the goal ("h" cost) to prioritize nodes. The algorithm guarantees finding the shortest path if the heuristic is admissible and the graph has no negative cycles. Pseudocode and Python code are provided to implement the A* algorithm to find the shortest path between nodes in a sample graph.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Practical-4

    4. Write a program to Implement A* Algorithm.

    A * Algorithm:
    The A* (pronounced "A star") algorithm is a widely-used pathfinding
    algorithm that finds the shortest path between two points in a weighted graph. It
    combines the cost of reaching a node from the start node (known as the "g" cost) and a
    heuristic estimate of the cost to reach the goal from that node (known as the "h" cost) to
    guide its search. The algorithm uses a priority queue to explore nodes efficiently and
    guarantees the shortest path if certain conditions are met.

    Algorithm:
    1. Initialize a priority queue (open set) and a set to keep track of visited nodes
    (closed set).
    2. Create a start node and add it to the open set. Set its "g" cost to 0.
    3. While the open set is not empty:
    I. Pop the node with the lowest combined cost ("g" cost + "h" cost) from
    the open set.
    II. If the current node is the goal node, reconstruct and return the path.
    III. Otherwise, mark the current node as visited by adding it to the closed
    set.

    4. For each neighbor of the current node that is not in the closed set:
    5. Calculate the tentative "g" cost from the start node to this neighbor.
    6. If the neighbor is not in the open set or the new "g" cost is lower than the
    existing one, update its "g" cost and set its parent as the current node.
    7. If the neighbor is not in the open set, calculate its "h" cost (heuristic estimate
    to the goal) and add it to the open set.
    8. If the open set becomes empty and the goal node has not been reached, there
    is no path. Exit with a "Path does not exist" message.
    9. End the algorithm.
     This algorithm efficiently explores the graph by prioritizing nodes with a
    lower estimated cost to reach the goal. It guarantees the shortest path when
    the following conditions are met:
     The heuristic function "h" is admissible (never overestimates the true cost).
     The graph does not have cycles with negative edge weights.
     The algorithm uses a consistent heuristic (satisfies the triangle inequality).
     The A* algorithm is widely used in various applications, including robotics,
    video games, and route planning, where finding the shortest path is crucial.
    Code:

    import heapq

    def aStarAlgo(graph, start, goal):


    open_set = [(0, start)] # Priority queue with (f_score, node)
    closed_set = set()

    g_scores = {node: float('inf') for node in graph}


    g_scores[start] = 0
    parent = {}

    while open_set:
    current_f, current_node = heapq.heappop(open_set)

    if current_node == goal:
    path = []
    while current_node in parent:
    path.append(current_node)
    current_node = parent[current_node]
    path.append(start)
    path.reverse()
    return path

    closed_set.add(current_node)

    if graph[current_node] is not None:


    for neighbor, weight in graph[current_node]:
    if neighbor in closed_set:
    continue

    tentative_g_score = g_scores[current_node] + weight

    if tentative_g_score < g_scores.get(neighbor, float('inf')):


    g_scores[neighbor] = tentative_g_score
    f_score = tentative_g_score + heuristic(neighbor, goal)
    parent[neighbor] = current_node
    heapq.heappush(open_set, (f_score, neighbor))

    return None

    def heuristic(node, goal):


    # In this example, we assume a simple heuristic: straight-line distance between nodes
    # You can replace this with a more accurate heuristic if needed
    return 0

    # Your corrected graph definition with 'G' node and connections


    Graph_node = {
    'A': [('B', 2), ('E', 3)],
    'B': [('C', 1), ('G', 9)],
    'C': None,
    'E': [('D', 6)],
    'D': [('G', 1)],
    'G': [],
    }
    start_node = 'A'
    goal_node = 'G'

    path = aStarAlgo(Graph_node, start_node, goal_node)

    if path:
    print(f"Shortest path from {start_node} to {goal_node}: {path}")
    else:
    print(f"No path found from {start_node} to {goal_node}")

    Output:

    You might also like