A* is probably my favourite graph search algorithm. Some 10+ years ago, I have implmented it with Excel and after that I have written a few more implementations. Just, not to repeat myself, I will not discuss it here. The reason for this article is the set of videos in YouTube, that I have started about Graph Algorithms. Thus, A* had to be presented there.
This article contains some of the other articles and nice music, seeing the code just working by itself in Excel:
The implementation in Python, actually steps upon the Dijkstra algorithm and changes it a bit. The code itself is here:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
def solve_a_star(data): lines = data.strip().split("\n") n_edges = int(lines[0].split()[1]) edge_lines = lines[1:1 + n_edges] node_lines = lines[1 + n_edges: -1] start, end = lines[-1].split() graph = {} heuristics = {} for line in node_lines: edge_name, heuristic_weight = line.split() heuristics[edge_name] = int(heuristic_weight) for line in edge_lines: u, v, w = line.split() if u not in graph: graph[u] = [] graph[u].append((v, int(w))) start_f = 0 + heuristics.get(start, 0) pq = [(start_f, start)] cost_so_far = {start: 0} came_from = {start: None} #A-star = g + h while pq: current_f, current_node = heapq.heappop(pq) if current_node == end: #Success! break best_known_g = cost_so_far[current_node] best_known_f = best_known_g + heuristics.get(current_node, 0) if current_f > best_known_f: continue for n, weight in graph.get(current_node, []): #n for neighbor new_g = cost_so_far[current_node] + weight if new_g < cost_so_far.get(n, float('inf')): cost_so_far[n] = new_g came_from[n] = current_node #highlight of A*: new_f = new_g + heuristics.get(n, 0) heapq.heappush(pq, (new_f, n)) path = [] if end in came_from: current = end while current: path.append(current) current = came_from[current] path.reverse() return path, cost_so_far |
The GitHub with the Jupyter Notebook and the complete input is there – https://github.com/Vitosh/Python_personal/blob/master/YouTube/048_Python-Graph/048-Graph-A-Star.ipynb
Thanks and enjoy! 🙂