A *寻路算法太慢

 Dir_Map = {
    "1": (1, 0),
    "2": (0, 1),
    "3": (-1, 0),
    "4": (0, -1),
    "5": (1, 1),
    "6": (-1, -1),
    "7": (1, -1),
    "8": (-1, 1)
}

class Node():
    def __init__(self, pos):
        self.x = pos[0]
        self.y = pos[1]
        self.g = 0
        self.h = 0
        self.f = 0
        self.beggining = 1
        self.parent = None

    def update(self, final):
        self.h = manhattan(self, final)
        self.f = self.f +  self.g    


class Child(Node):
    def __init__(self, x, y, parent):
        Node.__init__(self, (parent.x + x, parent.y + y))
        self.g = abs(x) + abs(y) + parent.g
        self.beggining = 0
        self.came_from = (parent.x, parent.y)
        self.parent = parent



def sortbyF(node):
    return node.f

def manhattan(current, final):
    return abs(current.x - final.x) + abs(current.y - final.y)

def check_List(list, successor):
    for ind, val in enumerate(list):
            if (val.x, val.y) == (successor.x, successor.y):
                if val.f < successor.f:
                    return 1
    return 0

openlist = []
closedlist = []

def recursion(node):
    if node.beggining is 0:
        closedlist.append(node.came_from)
        recursion(node.parent)


def pfind(grid, start, finish):

    start_node = Node((start[0], start[1]))
    finish_node = Node((finish[0], finish[1]))
    Stop = 0
    openlist.append(start_node)

    while len(openlist) is not 0:
        current = openlist.pop(0)


        for dirs in Dir_Map.values():
            suc = Child(dirs[0], dirs[1], current)

            if grid[suc.x][suc.y] is not 1 and suc.x <= len(grid[:][1]) and suc.y <= len(grid[1][:]):
                suc.update(finish_node)

                if (suc.x, suc.y) == finish:
                    #Added so it adds the last step.
                    #New suc.came_from = finish
                    suc = Child(dirs[0], dirs[1], suc)
                    #retrace the path.
                    recursion(suc)
                    closedlist.reverse()
                    return closedlist

                if check_List(openlist, suc):
                    continue

                openlist.append(suc)

            else:
                 continue

        openlist.sort(key=sortbyF)


    return None


grid = [[0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

print(pfind(grid, (0,0), (4,3)))
 

#1 楼

这里有一些合理的常规算法和特定于python的建议。

首先需要上的一课是，除非您知道要花时间在哪里，否则您不知道如何加快处理速度。值得学习使用python的cProfile或其他分析工具。

这里是您的示例分析器的运行。

C:\Users\Josiah\Desktop>python -m cProfile -s cumtime astar.py
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]
         6911416 function calls (6911411 primitive calls) in 8.103 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    8.103    8.103 {built-in method builtins.exec}
        1    0.000    0.000    8.103    8.103 astar.py:2(<module>)
        1    0.042    0.042    8.102    8.102 astar.py:59(pfind)
    15538    6.918    0.000    6.918    0.000 astar.py:43(check_List)
     2082    0.645    0.000    1.087    0.001 {method 'sort' of 'list' objects}
  6719169    0.442    0.000    0.442    0.000 astar.py:37(sortbyF)
    16658    0.019    0.000    0.031    0.000 astar.py:28(__init__)
    15539    0.008    0.000    0.018    0.000 astar.py:22(update)
    16660    0.010    0.000    0.010    0.000 astar.py:13(__init__)
    15539    0.008    0.000    0.010    0.000 astar.py:40(manhattan)
    64394    0.004    0.000    0.004    0.000 {built-in method builtins.abs}
    33161    0.003    0.000    0.003    0.000 {built-in method builtins.len}
     2083    0.002    0.000    0.002    0.000 {method 'pop' of 'list' objects}
     8494    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
     2083    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.__build_class__}
      6/1    0.000    0.000    0.000    0.000 astar.py:53(recursion)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 astar.py:12(Node)
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
        1    0.000    0.000    0.000    0.000 astar.py:27(Child)

cumtime是一个函数及其调用的所有函数所花费的时间。
tottime是该函数所花费的时间。 br />
您会看到，整个过程耗时8.1秒，其中的6.9直接花在check_List内部。这是整个程序运行时的85％，基本上是唯一值得优化的地方。毕竟，即使您没有其他时间花时间，您也只能将运行时间减少15％。您唯一的选择是少打check_List或使其更快。

check_List的目的是确定successor是否是迄今为止到达successor所处位置最快的方法。您可以通过遍历列表来完成此操作。维护和检查到目前为止您所看到的所有地方的字典会更快。

即将check_list更改为check_dict

def check_dict(openDict, successor):
    if (successor.x, successor.y) in openDict:
        return openDict[(successor.x, successor.y)].f < successor.f
    return False

而不是

            if check_List(openlist, suc):
                continue

            openlist.append(suc)

您想要

            if check_Dict(openDict, suc):
                continue

            openlist.append(suc)
            openDict[(suc.x, suc.y)] = suc

我的变化只用0.025秒而不是8.1的时间运行，除了上面用check_list替换check_dict之外没有任何变化。


您可能会注意到，这比85％的速度显着提高，这似乎很奇怪，因为15％的运行时间实际上根本不在check_list中。

碰巧的是，我的版本修复了一个我最初没有看到的细微错误。如上所述，check_list旨在防止您重新访问已经找到方法的节点。它通过详尽检查当前正在考虑的所有节点来进行下一步。但是，那是不一样的！由于current = openlist.pop(0)，您找到了一些到达的路线，但不再属于openlist！因为没有任何指标可以避免返回到它们，所以您会在早期节点之间来回跳动。

通过将弹出的每个节点分别存储在current中并在check_list中进行搜索来修补该错误，其性能几乎与使用字典一样。好吧，事实并非如此。在我的机器上需要0.125秒，比字典慢了整整五倍，并且随着图表变大，它会变得更糟。但这比8秒好得多！

#2 楼

如果容易获得迭代解决方案，请避免递归。以尾部递归的方式重写recursion：

def recursion(node):
    if node.beginning is not 0:
        return
    closedlist.append(node.came_from)
    recursion(node.parent)

并完全消除尾部递归： >作为特权，现在很清楚，recursion只是跟踪从节点向上的路径。适当地称呼它

def recursion(node):
    while node.beginning is 0:
        closedlist.append(node.came_from)
        node = node.parent

处理openlist看起来不是很理想。 br />在同一行中，每次迭代也会执行list.pop(0)，这也是对check_list的线性传递。 >

def trace_path(node):

循环。同时，该迭代为其添加了很少的节点（如果我没有记错的话，最多为8个）。这意味着您一直在对几乎排序的列表进行排序。通常，这不是最好的策略。所有这些，排序字典看起来比列表更有希望。

#3 楼

由于要提高性能，并且环境在相邻节点之间受到严格限制，因此不应使用通用图结构。例如。您可以使用网格存储已计算的每个节点的成本，以及使用类似的网格存储每个节点的父节点的引用或其他内容。

另外，不要对打开列表使用普通列表，因为如果您按照目前的朴素方法，则必须重复对其进行排序。 Python正是出于此目的而具有heapq模块或queue.PriorityQueue。然后，您将使用节点的成本+估计的启发式成本作为优先级值-Python会这样做：值越低，越高。此外，也可以在不使用封闭列表的情况下实现A *，这将消除您需要照顾的另一堆数据。一旦找到通往目标的道路。 IIRC您可以在目标成为公开列表的一部分后（在可允许的启发式方法的假设下）尽早终止。


我仍然坚持我对启发式功能的评论。您的代码。通常，您通常会希望将欧几里德距离用作网格世界。 Python还可以通过math模块中的hypot来高兴地支持您计算此距离。使用hypot(dx, dy)可能至少比sqrt(dx*dx + dy*dy)快一点，并且在数值上也更稳定。这些注释还描述了可能更适合这种情况的启发式方法。


附录

我拼凑了一些代码，这些代码仍然忽略了上面的一些建议，并且重用了一些结构性思想（例如Node类的修改版本），但是在产生相同结果的同时要快得多。另请注意，这在不使用关闭列表的实现中。

您原来的实现在我的机器上花费了大约12s。版本运行时间不到1毫秒。

 from heapq import heappush, heappop
from math import hypot, sqrt


SQRT2 = sqrt(2.0)


DIRECTIONS = ((1, 0, 1.0), (0, 1, 1.0), (-1, 0, 1.0), (0, -1, 1.0),
              (1, 1, SQRT2), (-1, -1, SQRT2), (1, -1, SQRT2), (-1, 1, SQRT2))


class Node:

    def __init__(self, x, y, cost=float("inf"), h=0, parent=None):
        self.x = x
        self.y = y
        self.cost = cost
        self.h = h
        self.parent = parent

    def update(self, new_parent, new_cost):
        self.parent = new_parent
        self.cost = new_cost

    def __repr__(self):
        return "Node(x={x}, y={y}, cost={cost}, h={h}, parent={parent})".format(**self.__dict__)

    @property
    def priority(self):
        return self.cost + self.h

    @property
    def pos(self):
        return self.x, self.y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __lt__(self, other):
        """This allows Node to be used in the priority queue directly"""
        return self.priority < other.priority


def make_grid(n_rows, n_cols, value):
    """Make a n_rows x n_cols grid filled with an initial value"""
    return [[value for _ in range(n_cols)] for _ in range(n_rows)]


def euclidean_distance(node1, node2):
    """Compute the Euclidean/L2 distance between two nodes"""
    return hypot(node1[0] - node2[0], node1[1] - node2[1])


def is_valid(x, y, grid, x_max, y_max):
    """Check the bounds and free space in the map"""
    if 0 <= x < x_max and 0 <= y < y_max:
        return grid[x][y] == 0
    return False


def pfind_new(grid, start, goal):
    x_max, y_max = len(grid), len(grid[0])

    # None will later be used as sentinel for "no node here (yet)"
    nodes = make_grid(x_max, y_max, None)

    start_node = Node(*start, cost=0, h=euclidean_distance(start, goal))
    nodes[start_node.x][start_node.y] = start_node
    goal_node = Node(*goal)
    nodes[goal_node.x][goal_node.y] = goal_node

    # openlist will be used a priority queue and has to be accessed using
    # heappush and heappop from the heapq module. The Node class was modified
    # to work well with this kind of datastructure.
    openlist = []
    heappush(openlist, start_node)

    found = False
    while not found:
        # get the node with the least overall cost (actual + heuristic)
        current = heappop(openlist)
        for direction in DIRECTIONS:
            # compute new coordinates
            x_n, y_n = current.x + direction[0], current.y + direction[1]
            if not is_valid(x_n, y_n, grid, x_max, y_max):
                continue
            # we have valid coordinates
            if nodes[x_n][y_n] is None:
                nodes[x_n][y_n] = Node(
                    x_n, y_n, h=euclidean_distance((x_n, y_n), goal)
                )
            # the new cost is made up if the current cost + transition
            new_cost = nodes[current.x][current.y].cost + direction[2]
            if new_cost < nodes[x_n][y_n].cost:
                # cool, we have found a faster path to this node, let's update
                # it's predecessor
                nodes[x_n][y_n].update(current.pos, new_cost)
                heappush(openlist, nodes[x_n][y_n])
                if nodes[x_n][y_n] == goal_node:
                    # we're done, get out of here
                    found = True
                    break
        # openlist is empty and we have not bailed out with found. seems like
        # there is nothing we can do here
        if not openlist:
            return []

    # backtracking
    path = []
    current = goal_node
    # this is a little bit weird because I decided to store only the
    # coordinates instead of the parent itself. Why? Because repr(node) is way
    #  more readable that way ;-)
    while True:
        path.append(current.pos)
        if current.parent is not None:
            current = nodes[current.parent[0]][current.parent[1]]
        else:
            break
    # the path is built by backtracking from the goal, so we have to reverse it
    return path[::-1]


if __name__ == "__main__":
    import timeit
    grid = [[0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 1, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0]]

    start = (0, 0)
    goal = (4, 3)
    t_start = timeit.default_timer()
    path = pfind_new(grid, start, goal)
    print(f"took: {timeit.default_timer() - t_start}")
    assert path == [(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]