上網睇過資料，A*係目前最高效率既search / path finding algorithm。成條algorithm既重點係列舉下一步既可能性，再假設自己係下一步入面，比較終點距離同埋上一步距離，最後計算得失。
以人類既角度解釋既話，比較似係一個人想走出迷宮，佢會一直望住個終點，睇下行邊步離終點直線距離會係最近。
當然，個heuristic function要根據唔同問題去改變，例如係呢個case，簡單既直線距離就夠。
本身我學校學過DFS、BFS、BST、Dijkstra，冇理由唔去識埋呢隻algorithm。
我想試下整好耐，但一直冇機會去做，但呢兩日終於無聊得濟斷斷續續搞掂佢。
#!/usr/bin/env python3
from time import time
from random import randint
SIZE = 20
BLOCKS = 100
class AStarGrid():
def __init__(self):
self.grid = AStarGrid.generate_grid()
def render_grid(self, path=None, goal=None):
for y in range(SIZE):
for x in range(SIZE):
p = (x, y,)
if path is not None and p in path:
print((len(path) - path.index(p)) % 10, end="")
elif self.grid[y][x]:
print("X", end="")
elif p == goal:
print("G", end="")
else:
print(".", end="")
print()
def generate_neighbors(self, p):
n = []
if p[0] - 1 >= 0:
n.append((p[0] - 1, p[1],))
if p[0] + 1 <= SIZE - 1:
n.append((p[0] + 1, p[1],))
if p[1] - 1 >= 0:
n.append((p[0], p[1] - 1,))
if p[1] + 1 <= SIZE - 1:
n.append((p[0], p[1] + 1,))
for cell in n:
if self.grid[cell[1]][cell[0]]:
n.remove(cell)
return n
def find_path_from(self, start, goal):
open_list, closed_list = [start], []
g, f, h, came_from = {}, {}, {}, {}
g[start] = 0
f[start] = AStarGrid.distance(start, goal)
h[start] = f[start]
while open_list:
parent = min(open_list, key=f.get)
if parent == goal:
return AStarGrid.reconstruct_path(came_from, goal)
open_list.remove(parent)
closed_list.append(parent)
for neighbor in self.generate_neighbors(parent):
if neighbor in closed_list:
continue
tmp_g = g[parent] + AStarGrid.distance(parent, neighbor)
better = False
if neighbor not in open_list:
open_list.append(neighbor)
better = True
elif tmp_g < g[neighbor]:
better = True
if better:
came_from[neighbor] = parent
g[neighbor] = tmp_g
h[neighbor] = AStarGrid.distance(neighbor, goal)
f[neighbor] = g[neighbor] + h[neighbor]
@staticmethod
def generate_grid():
grid = [[False] * SIZE for _ in range(SIZE)]
for i in range(BLOCKS):
x, y = randint(0, SIZE - 1), randint(0, SIZE - 1)
grid[y][x] = True
return grid
@staticmethod
def distance(p1, p2):
return (((p1[0] - p2[0]) ** 2) + ((p1[1] - p2[1]) ** 2)) ** 0.5
@staticmethod
def reconstruct_path(came_from, current_node):
path = []
while current_node in came_from:
current_node = came_from[current_node]
path.append(current_node)
return path
if __name__ == "__main__":
start = (0, 0,)
goal = (19, 19,)
grid = AStarGrid()
path = grid.find_path_from(start, goal)
grid.render_grid(path, goal)
結果
1.X.X...........X...
2..X.XX.X...X.......
3XX...X...........X.
4789XX....X.........
56X012...X.....X....
.XXX.34..........X..
X..X..5.....X..X....
.....X678X..X.......
........9........XX.
..X.XX.X0..X.....X..
.X......1.X...X.X...
X.......2X..X.XX....
.....XX.3456X.X..X.X
.X....X.X..7890....X
..XX..X...XXX.1XX...
X......X.....X2XX...
....XX....X...3XX...
X.X.X.........456789
.....X........X...X0
...XX..XX.X....X...G
./astar.py 0.07s user 0.01s system 98% cpu 0.077 total
同埋，唔好overestimate個cost，否則個result唔會再係shortest path。