不知道如何修复 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:

    if s[0] == ex and s[1] == ey:

        pass

    for sq in opensq:

        if sq[2] + sq[3] < s[2] + s[3]:

            successors.pop(successors.index(s))  # line 1

    for sq in closedsq:

        if sq[2] + sq[3] < s[2] + s[3]:

            successors.pop(successors.index(s))  # 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):

    if s[0] == ex and s[1] == ey:

        pass

    for sq in opensq + closedsq:

        if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:

            successors.pop(successors.index(s))

            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更整洁干净。

关闭列表可以参考维基百科伪代码后面的“ Remark ” ：

备注：在此伪代码中，如果一个节点通过一条路径到达，从 openSet 中删除，随后通过一条更便宜的路径到达，它将再次添加到 openSet。如果启发式函数是可接受的但不一致，这对于保证返回的路径是最优的是必不可少的。如果启发式是一致的，当一个节点从 openSet 中移除时，它的路径保证是最优的，因此如果再次到达该节点，测试 'tentative_gScore < gScore[neighbor]' 将始终失败。

GeeksForGeeks 上的封闭列表只有在启发式函数一致的情况下才是真正封闭的。