A*算法未能找到最短路径

Question

我正在尝试用Python实现A*算法，但在寻找这张地图的路径时遇到了问题：

X X X X X X X     S = Start
0 0 0 X 0 0 0     E = End
0 S 0 X 0 E 0     X = Wall
0 0 0 X 0 0 0
0 0 0 0 0 0 0

我使用的是曼哈顿方法。我的实现确实找到了路径，但不是最短的那条。错误发生在它的第二步——向右移动之后。这时它可以选择向上移动，估算的成本是四（向右三步，向下一步），或者向下移动（向右三步，向上一步）。有没有办法让它选择向下，以找到最短路径呢？

代码：

class Node:
    def __init__(self, (x, y), g, h, parent):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.f = g+h
        self.parent = parent

    def __eq__(self, other):
        if other != None:
            return self.x == other.x and self.y == other.y
        return False

    def __lt__(self, other):
        if other != None:
            return self.f < other.f
        return False

    def __gt__(self, other):
        if other != None:
            return self.f > other.f
        return True

    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ") " + str(self.f)

def find_path(start, end, open_list, closed_list, map, no_diag=True, i=1):
    closed_list.append(start)
    if start == end or start == None:
         return closed_list
     new_open_list = []
     for x, y in [(-1,1),(-1,-1),(1,-1),(1,1),(0,-1),(0,1),(-1,0),(1,0)]:
        full_x = start.x + x
        full_y = start.y + y
        g = 0
        if x != 0 and y != 0:
            if no_diag:
                continue
            g = 14
        else:
            g = 10
        h = 10 * (abs(full_x - end.x) + abs(full_y - end.y))
        n = Node((full_x,full_y),g,h,start)
        if 0 <= full_y < len(map) and 0 <= full_x < len(map[0]) and map[full_y][full_x] != 1 and n not in closed_list:
            if n in open_list:
                if open_list[open_list.index(n)].g > n.g:
                    new_open_list.append(n)
                else:
                    new_open_list.append(open_list[open_list.index(n)])
            else:
                new_open_list.append(n)
    if new_open_list == None or len(new_open_list) == 0:
        return find_path(start.parent, end, open_list, closed_list, map, no_diag, i-1)
    new_open_list.sort()
    return find_path(new_open_list[0], end, new_open_list, closed_list, map, no_diag)

Answer 1

你似乎是为每个节点都创建了一个新的开放列表，这个列表里只包含那个节点的邻居。这样做其实让你的搜索变成了一种深度优先搜索，而A*算法应该是最佳优先搜索。

你需要使用一个开放列表，并在访问每个节点时更新这个列表，加入该节点的邻居。开放列表中的旧节点必须保留在那里，直到它们被遍历并移到关闭列表中。

关于你在问题中提到的，先向上移动再向下移动是可以的（因为根据启发式算法，它们离目标的距离是一样的）。重要的是，最后选择的路径是最短的。