不知道如何修复 A* 寻路算法

Question

我正在尝试GeeksforGeeks 的 A* 大纲。我遵循了灰色框中的大部分步骤，直到我在 dii 和 diii 上遇到了障碍。这是寻路部分：

def pathfind(grid):

    sx, sy = 0, 0

    # find start point and end point cood

    for y in range(len(grid)):

        for x in range(len(grid[y])):

            if grid[y][x] == "S":

                sx = x

                sy = y

            elif grid[y][x] == "E":

                ex = x

                ey = y

    opensq = []

    closedsq = []

    successor = []

    #add starting point to closed

    opensq.append([sx, sy, gcost(sx, sy, sx, sy), hcost(sx, sy, ex, ey)])

    grid[sy][sx] = "O"

    while opensq:

        # find the node with lowest fcost

        q = opensq[0]

        if len(opensq) == 1:

            pass

        else:

            for sq in range(len(opensq)):

                if sq == len(opensq) - 1:

                    pass

                else:

                    if q[2] + q[3] < opensq[sq + 1][2] + opensq[sq + 1][3]:

                        pass

                    elif q[2] + q[3] == opensq[sq + 1][2] + opensq[sq + 1][3]:

                        # if f is same, check hcost

                        if q[3] < opensq[sq + 1][3]:

                            pass

                        elif q[3] == opensq[sq + 1][3]:

                            pass

                        else:

                            q = opensq[sq + 1]

                    else:

                        q = opensq[sq + 1]

        opensq.pop(opensq.index(q))

        # pick successors to q

        successors = []

        successors.append([q[0] + 1, q[1], gcost(q[0] + 1, q[1], sx, sy), hcost(q[0] + 1, q[1], ex, ey)])

        successors.append([q[0] - 1, q[1], gcost(q[0] - 1, q[1], sx, sy), hcost(q[0] - 1, q[1], ex, ey)])

        successors.append([q[0], q[1] + 1, gcost(q[0], q[1] + 1, sx, sy), hcost(q[0], q[1] + 1, ex, ey)])

        successors.append([q[0], q[1] - 1, gcost(q[0], q[1] - 1, sx, sy), hcost(q[0], q[1] - 1, ex, ey)])

Answer 1

错误发生在以下部分：for s in successors:&nbsp; &nbsp; if s[0] == ex and s[1] == ey:&nbsp; &nbsp; &nbsp; &nbsp; pass&nbsp; &nbsp; for sq in opensq:&nbsp; &nbsp; &nbsp; &nbsp; if sq[2] + sq[3] < s[2] + s[3]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; successors.pop(successors.index(s))&nbsp; # line 1&nbsp; &nbsp; for sq in closedsq:&nbsp; &nbsp; &nbsp; &nbsp; if sq[2] + sq[3] < s[2] + s[3]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; successors.pop(successors.index(s))&nbsp; # line 2在“第1行”和“第2行”上，可以在循环中的上一个循环中已经弹出successors.index(s)之后调用。然后，发生错误。sfor而且，更重要的是，您的代码没有正确执行A* 搜索算法。当您对代码发表评论时，您应该只检查“与后继位置相同的节点”。您可以尝试使用以下代码代替上述部分来解决问题。# Iterate over a copy of the list,# since we are popping elements in the original list.for s in list(successors):&nbsp; &nbsp; if s[0] == ex and s[1] == ey:&nbsp; &nbsp; &nbsp; &nbsp; pass&nbsp; &nbsp; for sq in opensq + closedsq:&nbsp; &nbsp; &nbsp; &nbsp; if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; successors.pop(successors.index(s))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break而且，上面的代码并不是那么简洁。你可以看到上面的语句sq[3] == s[3]总是成立，if因为它们是hcost相同的位置。所以，你可以比较sq[2]，s[2]即gcost。（换句话说，因为sq[3] == s[3]持有，你可以只做sq[2] <= s[2]而不是上面的sq[2] + sq[3] <= s[2] + s[3]陈述。）我认为GeeksforGeeks 上if灰色框中描述的 A* 搜索算法不是那么简洁。gcost是“从起点移动到网格上给定方格的移动成本，沿着生成的路径到达那里。” 所以你应该修复你的代码：移除gcost功能修复gcost用于opensq.append([sx, sy, 0, hcost(sx, sy, ex, ey)])successors.append([q[0] + 1, q[1], q[2] + 1, hcost(q[0] + 1, q[1], ex, ey)])successors.append([q[0] - 1, q[1], q[2] + 1, hcost(q[0] - 1, q[1], ex, ey)])successors.append([q[0], q[1] + 1, q[2] + 1, hcost(q[0], q[1] + 1, ex, ey)])successors.append([q[0], q[1] - 1, q[2] + 1, hcost(q[0], q[1] - 1, ex, ey)])通过上述修复，您的代码似乎可以正常工作。但我认为你仍然可以改进你的代码。我们可以改进的一件事是分离节点和gcost节点的。现在opensq在您的代码中保存节点坐标并保存在一起，如果计算的不同，则可以多次gcost添加一个节点。opensqgcost你也可以参考Wikipedia 上的 A* 伪代码。我认为它比您已经提到的GeeksForGeeks更整洁干净。你也可以参考Wikipedia 上的 A* 伪代码。我认为它比您已经提到的GeeksForGeeks更整洁干净。关闭列表可以参考维基百科伪代码后面的“&nbsp;Remark&nbsp;”&nbsp;：备注：在此伪代码中，如果一个节点通过一条路径到达，从 openSet 中删除，随后通过一条更便宜的路径到达，它将再次添加到 openSet。如果启发式函数是可接受的但不一致，这对于保证返回的路径是最优的是必不可少的。如果启发式是一致的，当一个节点从 openSet 中移除时，它的路径保证是最优的，因此如果再次到达该节点，测试 'tentative_gScore < gScore[neighbor]' 将始终失败。GeeksForGeeks 上的封闭列表只有在启发式函数一致的情况下才是真正封闭的。