G

## All 5 pathfinders

public
Guest Nov 27, 2023 Never
Python PathFinderOtimized.py 148 lines (116 loc) | 4.82 KB
``1from queue import Queue, LifoQueue, PriorityQueue2 3INFINITY = float("inf")4 5def print_node_info(current_node, path_cost, path):6    print("Visiting: ", current_node, " Path Cost: ", path_cost, " Path: ", path)7 8def bfs(graph, start, end, UCS=False, start_node=None):9    queue = Queue() if not UCS else PriorityQueue()10    visited = []11    queue.put((0, start, [start]) if start_node is None else (0, start_node, [start_node]))12 13    while not queue.empty():14        path_cost, current_node, path = queue.get()15        if current_node in visited:16            continue17        visited.append(current_node)18 19        print_node_info(current_node, path_cost, path) if start_node is None else None20 21        if current_node == end:22            print(f"Goal Reached! Cost: ", path_cost) if start_node is None else None23            break24 25        for neighbor, weight in graph[current_node].items():26            if neighbor not in visited:27                new_path_cost = path_cost + weight28                new_path = path + [neighbor]29                queue.put((new_path_cost, neighbor, new_path))30        31        print("Frontier: ", end="")32        for frontier in queue.queue:33            print((frontier,frontier), end=" ")34        print()35    36    return path_cost37 38def gbfs(graph, start, end, heuristic):39    queue = PriorityQueue()40    visited = []41    queue.put((heuristic[start], 0, start, [start]))42 43    while not queue.empty():44        h_cost, path_cost, current_node, path = queue.get()45        if current_node in visited:46            continue47        visited.append(current_node)48 49        print_node_info(current_node, path_cost, path)50 51        if h_cost == INFINITY:52            continue53 54        if current_node == end:55            print(f"Goal Reached! Cost: ", path_cost)56            break57 58        for neighbor, weight in graph[current_node].items():59            if neighbor not in visited:60                new_path_cost = path_cost + weight61                new_path = path + [neighbor]62                queue.put((heuristic[neighbor], new_path_cost, neighbor, new_path))63 64def asearch(graph, start, end, astar=False, heuristic=None):65    queue = PriorityQueue()66    visited = []67    queue.put((heuristic[start], 0, start, [start]))68    hs_history = {}69 70    while not queue.empty():71        h_cost, path_cost, current_node, path = queue.get()72        if current_node in visited:73            continue74        visited.append(current_node)75 76        print_node_info(current_node, path_cost, path)77 78        if astar:79            hs_history[current_node] = bfs(graph, start, end, UCS=True, start_node=current_node)80 81        if h_cost == INFINITY:82            continue83 84        if current_node == end:85            print(f"Goal Reached! Cost: ", path_cost)86            break87 88        for neighbor, weight in graph[current_node].items():89            if neighbor not in visited:90                new_path_cost = path_cost + weight91                new_path = path + [neighbor]92                total_cost = new_path_cost + heuristic[neighbor]93                queue.put((total_cost, new_path_cost, neighbor, new_path))94    95    return hs_history96 97def astarsearch(graph, start, end, heuristic):98    hs_history = asearch(graph, start, end, astar=True, heuristic=heuristic)99    for node, hs in hs_history.items():100        if hs > heuristic[node]:101            print(f"Not admissible h*(n)={hs} > h(n)={heuristic[node]}")102        else:103            print(f"Admissible h*(n)={hs} > h(n)={heuristic[node]}")104 105def dfs(graph, start, end):106    stack = LifoQueue()107    visited = []108    stack.put((start, [start], 0))109 110    while not stack.empty():111        current_node, path, path_cost = stack.get()112 113        if current_node in visited:114            continue115        visited.append(current_node)116 117        print_node_info(current_node, path_cost, path)118 119        if current_node == end:120            print(f"Goal Reached! Cost: ", path_cost)121            break122 123        for neighbor, weight in graph[current_node].items():124            if neighbor not in visited:125                new_path_cost = path_cost + weight126                new_path = path + [neighbor]127                stack.put((neighbor, new_path, new_path_cost))128 129if __name__ == "__main__":130    graph = {131    'S': {'A': 5, 'B': 3, 'C': 4},132    'A': {'C': 2},133    'B': {'C': 1},134    'C': {'D': 3, 'E': 5, 'F': 10},135    'D': {},136    'E': {},137    'F': {'G': 12, 'H': 9},138    'G': {},139    'H': {'G': 1}140    }141    heuristic_values = {'S': 10, 'A': 9, 'B': 7, 'C': 8, 'D': INFINITY, 'E': INFINITY, 'F': 5, 'G': 0, 'H': 2}142 143    bfs(graph, 'S', 'G')144    dfs(graph, 'S', 'G')145    bfs(graph, 'S', 'G', UCS=True)146    gbfs(graph, 'S', 'G', heuristic_values)147    asearch(graph, 'S', 'G', heuristic_values)148    astarsearch(graph, 'S', 'G', heuristic_values)``