我如何使我的A星级搜索算法更有效？

问题描述 投票：0回答：2

我在matplotlib中有一个网格（根据用户的选择为20 * 20或40 * 40），其中包含根据LatLong位置划分的数据。该网格中的每个单元格代表0.002或0.001的区域（例如：[-70.55, 43.242]至[-70.548, 43.244]）。网格基于阈值进行着色，例如高于30的部分为绿色，低于30的部分为红色。

我实施了A起始算法，以从该图上的一个位置（单元）转到另一个位置，同时避免所有绿色单元。在绿色和红色单元格的边界上行驶的成本为1.3，对角线成本为1.5，在两个红色单元格之间的行驶成本为1。

我正在使用对角线距离启发法，对于每个像元，我将获取所有可能的邻居并根据阈值设置其G值。

现在，我大部分时间都能获得正确的路径，对于附近的牢房，它的运行时间不到1秒。但是当我走得更远时，需要14-18秒。

我不明白我在这里做什么错？我一直在尝试找出一种改进方法，但是失败了。

这里是算法的一部分。我想指出的是，此处确定可访问的邻居并设置G值可能不会发出问题，因为每个函数调用的运行时间约为0.02-0.03秒。

任何建议，不胜感激！谢谢

def a_star(self, start, end):
    startNode = Node(None, start)
    endNode = Node(None, end)
    openList = []
    closedList = []
    openList.append(startNode)

    while len(openList) > 0:

        current = openList[0]
        if current.location == endNode.location:
            path = []
            node = current
            while node is not None:
                path.append(node)
                node = node.parent
            return path[::-1]

        openList.pop(0)
        closedList.append(current)

       # This takes around 0.02 0.03 seconds
        neighbours = self.get_neighbors(current)

        for neighbour in neighbours:
            append = True
            for node in closedList:
                if neighbour.location == node.location:
                    append = False
                    break
            for openNode in openList:
                if neighbour.location == openNode.location:
                    if neighbour.g < openNode.g:
                        append = False
                        openNode.g = neighbour.g
                        break
            if append:

                neighbour.h = round(self.heuristic(neighbour.location, endNode.location), 3)
                neighbour.f = round(neighbour.g + neighbour.h, 3)

                bisect.insort_left(openList, neighbour)
    return False

编辑：添加节点片段

 class Node:
    def __init__(self, parent, location):
        self.parent = parent
        self.location = location
        self.g = 0
        self.h = 0
        self.f = 0

编辑2：添加图像

circle is start location, star is destination. Yellow cells are not accessible, so no diagonal path on yellow cells, and cannot travel between two yellow cells.

圆圈是起始位置，星号是目的地。黄色单元格不可访问，因此黄色单元格上没有对角线路径，并且不能在两个黄色单元格之间移动。

python algorithm matplotlib search a-star
2个回答
0
投票

这部分非常效率低下。对于您遍历两个相对较大的列表的每个邻居，一旦列表开始增长，这就会使总体复杂度非常高：

for node in closedList:
    if neighbour.location == node.location:
        append = False
        break
for openNode in openList:
    if neighbour.location == openNode.location:

基本上，您的算法不应依赖于任何列表。您有自己的单元格，从列表中弹出一个单元格，得到8个邻居，通过与您拥有的单元格进行比较来处理它们，然后将其中一些添加到列表中。无需遍历任何列表。

0
投票

正如@lenic已经指出的那样，您拥有的内部循环不属于A *算法。

第一个（for node in closedList）应该替换为检查节点是否在集合中（而不是列表中：这样就不需要迭代。）>

使用无穷初始化所有openNode in openList属性值（起始节点除外）时，不需要第二个（g）。然后，您可以将新的g值与neighbor节点中已经存储的值进行比较。

此外，我建议在创建图形后立即为整个图形创建节点。当您需要在同一张图上进行多个查询时，这将是有益的。

此外，我建议使用bisect.insort_left代替heapq.heappush。这样会更快，因为它不会真正对队列进行完全排序，而只是确保可以维护heap属性。虽然时间复杂度是相同的。更重要的是，获取

从中获得下一个值的时间复杂度优于openList.pop(0)。

我建议使用成本10、13和15而不是1、1.3和1.5，因为整数运算没有精度问题。

出于相同的原因，我将不使用分数位置坐标。由于它们之间的距离相等（例如0.002），因此我们可以对两个坐标都使用连续整数（0、1、2，...）。额外的函数可以使用解和参考坐标对将这些整数坐标转换回“世界”坐标。

我做了一些假设：

  • 严禁通过“敌对”牢房。没有边缘可以穿过这些边缘。例如，如果起始位置在四个敌对牢房的中间，则将没有路径。可以考虑一种替代方法，其中这些边的成本会非常高，因此您始终可以提出一条路径。

  • 网格边界上的直边全部允许。当与其相邻的单个牢房充满敌意时，它们的成本将为1.3（13）。因此，实际上在两个维度中，每个位置都比单元格多一个位置

  • 阈值输入将是0到1之间的分数，表示相对于单元总数应友好的单元分数，并且该值将转换为“ split”值以区分友好和敌对的细胞。

    • 这是您可以用作启发的代码：

from heapq import heappop, heappush

class Node:
    def __init__(self, location):
        self.location = location
        self.neighbors = []
        self.parent = None
        self.g = float('inf')
        self.f = 0

    def clear(self):
        self.parent = None
        self.g = float('inf')
        self.f = 0

    def addneighbor(self, cost, other):
        # add edge in both directions
        self.neighbors.append((cost, other))
        other.neighbors.append((cost, self))

    def __gt__(self, other):  # make nodes comparable
        return self.f > other.f

    def __repr__(self):
        return str(self.location)

class Graph:
    def __init__(self, grid, thresholdfactor):
        # get value that corresponds with thresholdfactor (which should be between 0 and 1)
        values = sorted([value for row in grid for value in row])
        splitvalue = values[int(len(values) * thresholdfactor)]
        print("split at ", splitvalue)
        # simplify grid values to booleans and add extra row/col of dummy cells all around
        width = len(grid[0]) + 1
        height = len(grid) + 1
        colors = ([[False] * (width + 1)] +
            [[False] + [value < splitvalue for value in row] + [False] for row in grid] +
            [[False] * (width + 1)])

        nodes = []
        for i in range(height):
            noderow = []
            nodes.append(noderow)
            for j in range(width):
                node = Node((i, j))
                noderow.append(node)
                cells = [colors[i+1][j]] + colors[i][j:j+2]  # 3 cells around location: SW, NW, NE
                for di, dj in ((1, 0), (0, 0), (0, 1), (0, 2)):  # 4 directions: W, NW, N, NE
                    cost = 0
                    if (di + dj) % 2:  # straight
                        # if both cells are hostile, then not allowed
                        if cells[0] or cells[1]:  # at least one friendly cell
                            # if one is hostile, higher cost
                            cost = 13 if cells[0] != cells[1] else 10
                        cells.pop(0)
                    elif cells[0]:  # diagonal: cell must be friendly
                        cost = 15
                    if cost:
                        node.addneighbor(cost, nodes[i-1+di][j-1+dj])
        self.nodes = nodes

    @staticmethod
    def reconstructpath(node):
        path = []
        while node is not None:
            path.append(node)
            node = node.parent
        path.reverse()
        return path

    @staticmethod
    def heuristic(a, b):
        # optimistic score, assuming all cells are friendly
        dy = abs(a[0] - b[0])
        dx = abs(a[1] - b[1])
        return min(dx, dy) * 15 + abs(dx - dy) * 10

    def clear(self):
        # remove search data from graph 
        for row in self.nodes:
            for node in row:
                node.clear()

    def a_star(self, start, end):
        self.clear()
        startnode = self.nodes[start[0]][start[1]]
        endnode = self.nodes[end[0]][end[1]]
        startnode.g = 0
        openlist = [startnode] 
        closed = set()
        while openlist:
            node = heappop(openlist)
            if node in closed:
                continue
            closed.add(node)
            if node == endnode:
                return self.reconstructpath(endnode)
            for weight, neighbor in node.neighbors:
                g = node.g + weight
                if g < neighbor.g:
                    neighbor.g = g
                    neighbor.f = g + self.heuristic(neighbor.location, endnode.location)
                    neighbor.parent = node
                    heappush(openlist, neighbor)

我将您包含的图形编码为图像，以查看代码的行为方式：
grid = [
    [38, 32, 34, 24,  0, 82,  5, 41, 11, 32,  0, 16,  0,113, 49, 34, 24,  6, 15, 35],
    [61, 61,  8, 35, 65, 31, 53, 25, 66,  0, 21,  0,  9,  0, 31, 75, 20,  8,  3, 29],
    [43, 66, 47,114, 38, 41,  1,108,  9,  0,  0,  0, 39,  0, 27, 72, 19, 14, 24, 25],
    [45,  5, 37, 23,102, 25, 49, 34, 41, 49, 35, 15, 29, 21, 66, 67, 44, 31, 38, 91],
    [47, 94, 48, 69, 33, 95, 18, 75, 28, 70, 38, 78, 48, 88, 21, 66, 44, 70, 75, 23],
    [23, 84, 53, 23, 92, 14, 71, 12,139, 30, 63, 82, 16, 49, 76, 56,119,100, 47, 21],
    [30,  0, 32, 90,  0,195, 85, 65, 18, 57, 47, 61, 40, 32,109,255, 88, 98, 39,  0],
    [ 0,  0,  0,  0, 39, 39, 76,167, 73,140, 58, 56, 94, 61,212,222,141, 50, 41, 20],
    [ 0,  0,  0,  5,  0,  0, 21,  2,132,100,218, 81,  0, 62,135, 42,131, 80, 14, 19],
    [ 0,  0,  0,  0,  0, 15,  9, 55, 70, 71, 42,117, 65, 63, 59, 81,  4, 40, 77, 46],
    [ 0,  0,  0,  0, 55, 52,101, 93, 30,166, 56, 19, 76,103, 54, 37, 24, 23, 59, 98],
    [ 0,  0,  0,  0,  9,  9, 44,149, 11,134, 90, 64, 44, 57, 61, 79,270,201, 84,  6],
    [ 0,  0,  0, 22,  1, 15,  0, 25, 30,101,154, 60, 97, 64, 15,162, 27, 91, 71,  0],
    [ 0,  0,  1, 35,  5, 10,  0, 55, 25,  0,200, 81, 31, 53, 42, 74,127,154,  7,  0],
    [ 0,  0,187, 17, 45, 66, 91,191, 70,189, 18, 25, 67, 32, 40, 79,103, 79, 59,  0],
    [ 0, 21, 16, 14, 19, 58,278, 56,128, 95,  3, 52,  9, 27, 25, 43, 62, 25, 38,  0],
    [ 4,  3, 11, 26,119,165, 53, 85, 46, 81, 19, 11, 12, 19, 18,  9, 16,  6, 37,  0],
    [ 5,  0,  0, 65,158,153,118, 38,123, 46, 28, 24,  0, 21, 11, 20,  5,  1, 10,  0],
    [17,  4, 28, 81,101,101, 46, 25, 44, 12, 41,  6, 27,  8,  4, 32, 40,  1,  1,  0],
    [26, 20, 84, 42,112, 27, 14, 16,  5, 13,  3, 43,  6, 18, 12, 44,  5,  0,  0,  5]
]

graph = Graph(grid, 0.5) # provide the threshold at initialisation
path = graph.a_star((7, 4), (14, 18))
print(path)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.