試下用python整A* search

上網睇過資料,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]

    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

    def distance(p1, p2):
        return (((p1[0] - p2[0]) ** 2) + ((p1[1] - p2[1]) ** 2)) ** 0.5

    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。

Recommendations

Last modified: 2016-06-17 11:08:04
Powered by Simple Blog