Python A* 算法搜索不当

Question

我正在尝试用Python实现A*算法。我的算法可以顺利找到目标路径，但当我让程序可视化“关闭列表”和“开放列表”时，我发现关闭列表在遇到复杂障碍物时，会变成一个大大的完美菱形。换句话说，我的算法在关闭列表中添加了一些节点，这些节点离目标的距离比“预期”关闭列表的邻居要远得多。

举个例子，当关闭列表中的一个点距离目标是(2, 1)，但有一堵墙挡住了路，算法会添加一个距离目标(2, 2)的节点（试图越过墙），还有一个距离目标(3, 1)的节点……这完全没有理由，因为显然后者更远。

我不太确定我哪里出错了。这个距离计算是用“曼哈顿方法”来做的（虽然对我来说不太完美，但不应该导致这么大的问题），而且其他方法也出现了同样的问题（甚至更糟）。

def distance(self, tile1, tile2):
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
    self.totalDist = self.straightCost * (self.xDist + self.yDist)
    return self.totalDist

填充关闭列表的代码大致是这样的。在这里，.score2是H值，是用上面提到的距离方法计算的。

    while self.endTile not in self.openList:
        self.smallestScore = MAX_DIST * 50
        self.bestTile = None
        for tile in self.openList:
            if tile.score[2] <= self.smallestScore:
                self.bestTile = tile
                self.smallestScore = tile.score[2]
        self.examine(self.bestTile)

“检查”函数会将检查过的方块添加到关闭列表，并将它的可行邻居添加到开放列表，似乎运行得很好。算法似乎接受所有H值为X的方块（X的值会根据目标所在迷宫的复杂程度而变化）。

慢慢来逐个节点可视化，基本上可以看到它填充了一个大小为X的区域，并在进入迷宫的入口被填充时找到路径。我真的不知道我哪里做错了，已经尝试了两天来解决这个问题。

编辑：为了更好地解决问题，这里有一段更完整的代码。这是examine()函数：

def examine(self, tile):
    #Add the tile to the closed list, color it in, remove it from open list.
    self.closedList.append(tile)
    tile.color = CLOSED
    pygame.draw.rect(windowSurface, tile.color, tile.rect)
    pygame.display.update(tile.rect)
    self.openList.remove(tile)
    #Search all neighbors.
    for a, b in ((tile.col + 1, tile.row), (tile.col - 1, tile.row),
                 (tile.col + 1, tile.row + 1), (tile.col + 1, tile.row - 1),
                 (tile.col - 1, tile.row + 1), (tile.col - 1, tile.row - 1),
                 (tile.col, tile.row + 1), (tile.col, tile.row - 1)):
        #Ignore if out of range.
        if a not in range(GRID_WIDTH) or b not in range(GRID_HEIGHT):
            pass
        #If the neighbor is pathable, add it to the open list.
        elif self.tileMap[b][a].pathable and self.tileMap[b][a] not in self.openList and self.tileMap[b][a] not in self.closedList:
            self.where = abs((a - tile.col)) + abs((b - tile.row))
            if self.where == 0 or self.where == 2:
                self.G = tile.score[1] + self.diagCost
                self.H = self.distance(self.endTile, self.tileMap[b][a])
                self.F = self.G + self.H
            elif self.where == 1:
                self.G = tile.score[1] + self.straightCost
                self.H = self.distance(self.endTile, self.tileMap[b][a])
                self.F = self.G + self.H

            #Append to list and modify variables.
            self.tileMap[b][a].score = (self.F, self.G, self.H)
            self.tileMap[b][a].parent = tile
            self.tileMap[b][a].color = OPEN
            pygame.draw.rect(windowSurface, self.tileMap[b][a].color, self.tileMap[b][a].rect)
            pygame.display.update(self.tileMap[b][a].rect)
            self.openList.append(self.tileMap[b][a])
        #If it's already in one of the lists, check to see if this isn't a better way to get to it.
        elif self.tileMap[b][a] in self.openList or self.tileMap[b][a] in self.closedList:
            self.where = abs((a - tile.col)) + abs((b - tile.row))
            if self.where == 0 or self.where == 2:
                if tile.score[1] + self.diagCost < self.tileMap[b][a].score[1]:
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.diagCost, self.tileMap[b][a].score[2])
                    self.tileMap[b][a].parent = tile
                    print "parent changed!"
            elif self.where == 1:
                if tile.score[1] + self.straightCost < self.tileMap[b][a].score[1]:
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.straightCost, self.tileMap[b][a].score[2])
                    self.tileMap[b][a].parent = tile
                    print "parent changed!"

这是一个更新版本的迭代，速度放慢了，这样我可以观察它的进展。它的目的是找到得分最低的节点[0]（得分是F、G、H得分的元组）。

def path(self):
    self.openList.append(self.startTile)
    self.startTile.score = (self.distance(self.startTile, self.endTile), 0, self.distance(self.startTile, self.endTile))
    self.examine(self.openList[0])
    self.countDown = 0
    while self.endTile not in self.openList:
        if self.countDown <= 0:
            self.countDown = 5000
            self.smallestScore = MAX_DIST * 50
            self.bestTile = self.startTile
            for tile in self.openList:
                if tile.score[0] <= self.smallestScore:
                    self.bestTile = tile
                    self.smallestScore = tile.score[0]
            self.examine(self.bestTile)
        else:
            self.countDown -= timePassed

以下是一个图像，展示了多余的搜索区域，使用了self.totalDist = self.diagCost * math.sqrt(pow(self.xDist, 2) + pow(self.yDist, 2))

另外，从公式中去掉TILE_SIZE常量也得到了一个同样看起来效率不高的搜索区域：

我觉得它不应该搜索那么多额外的区域——只需搜索障碍物周围的区域就可以了。

Answer 1

我的想法是：这是因为在这种情况下，曼哈顿距离并不< a href="http://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow">符合可接受性，因为你还可以斜着移动。

试试这个：

def distance(self, tile1, tile2):
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
    self.totalDist = self.diagCost * math.sqrt(self.xDist*self.xDist + self.yDist*self.yDist)
                     # or it might be self.straightCost, depending on their values.
                     # self.diagCost is probably right, though.
    return self.totalDist