Untitled
unknown
plain_text
5 months ago
2.5 kB
3
Indexable
import pandas as pd # Define the graph as adjacency list with weights graph = { 'S': {'A': 2, 'D': 3}, 'A': {'S': 2, 'B': 3, 'D': 2}, 'B': {'A': 3, 'C': 3}, 'C': {'B': 3, 'G': 5}, 'D': {'S': 3, 'A': 2, 'E': 6}, 'E': {'D': 6, 'F': 1}, 'F': {'E': 1, 'G': 2}, 'G': {'C': 5, 'F': 2} } # Define the heuristic values heuristic = { 'S': 8, 'A': 6, 'B': 5, 'C': 3, 'D': 6, 'E': 3, 'F': 1, 'G': 0 } # A* Algorithm implementation def a_star_search(graph, heuristic, start, goal): open_list = {start: (0 + heuristic[start])} # Open list with initial node and its f(n) value closed_list = set() # Closed list g_values = {start: 0} # Cost from start to node parent = {start: None} # To reconstruct the path while open_list: # Get the node with the lowest f(n) value current_node = min(open_list, key=open_list.get) current_f_value = open_list[current_node] # If goal is reached, reconstruct the path if current_node == goal: path = [] while current_node: path.append(current_node) current_node = parent[current_node] path.reverse() return path, g_values[goal] # Return the path and its cost # Move current_node from open to closed list del open_list[current_node] closed_list.add(current_node) # Check neighbors of the current node for neighbor, cost in graph[current_node].items(): if neighbor in closed_list: continue # Skip if neighbor is in closed list # Calculate tentative g value for the neighbor tentative_g = g_values[current_node] + cost if neighbor not in open_list or tentative_g < g_values.get(neighbor, float('inf')): g_values[neighbor] = tentative_g # Update g value f_value = tentative_g + heuristic[neighbor] # Calculate f value open_list[neighbor] = f_value # Add/update neighbor in open list parent[neighbor] = current_node # Update parent return None, float('inf') # Return None if no path is found # Perform A* search from S to G path, cost = a_star_search(graph, heuristic, 'S', 'G') # Prepare results for display results = { "Path": [path], "Total Cost": [cost] } df_results = pd.DataFrame(results) import ace_tools as tools; tools.display_dataframe_to_user(name="A* Algorithm Path and Cost", dataframe=df_results)
Editor is loading...
Leave a Comment