G

All 5 pathfinders

public
Guest Nov 20, 2023 Never 22
Clone
Python PathFinderOtimized.py 148 lines (116 loc) | 4.82 KB
1
from queue import Queue, LifoQueue, PriorityQueue
2
3
INFINITY = float("inf")
4
5
def print_node_info(current_node, path_cost, path):
6
print("Visiting: ", current_node, " Path Cost: ", path_cost, " Path: ", path)
7
8
def 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
continue
17
visited.append(current_node)
18
19
print_node_info(current_node, path_cost, path) if start_node is None else None
20
21
if current_node == end:
22
print(f"Goal Reached! Cost: ", path_cost) if start_node is None else None
23
break
24
25
for neighbor, weight in graph[current_node].items():
26
if neighbor not in visited:
27
new_path_cost = path_cost + weight
28
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[1],frontier[0]), end=" ")
34
print()
35
36
return path_cost
37
38
def 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
continue
47
visited.append(current_node)
48
49
print_node_info(current_node, path_cost, path)
50
51
if h_cost == INFINITY:
52
continue
53
54
if current_node == end:
55
print(f"Goal Reached! Cost: ", path_cost)
56
break
57
58
for neighbor, weight in graph[current_node].items():
59
if neighbor not in visited:
60
new_path_cost = path_cost + weight
61
new_path = path + [neighbor]
62
queue.put((heuristic[neighbor], new_path_cost, neighbor, new_path))
63
64
def 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
continue
74
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
continue
83
84
if current_node == end:
85
print(f"Goal Reached! Cost: ", path_cost)
86
break
87
88
for neighbor, weight in graph[current_node].items():
89
if neighbor not in visited:
90
new_path_cost = path_cost + weight
91
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_history
96
97
def 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
105
def 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
continue
115
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
break
122
123
for neighbor, weight in graph[current_node].items():
124
if neighbor not in visited:
125
new_path_cost = path_cost + weight
126
new_path = path + [neighbor]
127
stack.put((neighbor, new_path, new_path_cost))
128
129
if __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)