python - 将 A* 与目标外部图一起使用

Question

我的目标是找到 A 和 B 之间的最短路径，但 B 可能在已知图之外。目前我的成本函数运行良好，启发式函数是 3D 欧几里德函数。

为了解决目标可能在图表之外的问题，我尝试在优先级值停止改变某个时间时退出算法，但这没有用。该算法吐出一条随机路径。

我不选择最接近目标的节点的原因是，如果我选择该算法，那么它肯定会尝试到达该点。在我的应用程序中，当新信息出现时，我将重新运行算法(即更新可能包含目标的图表)。

所以我需要的是找到一条最接近图外目标且成本最小的路径。我不期望有代码或任何内容作为答案，但非常感谢任何有关如何解决此类问题的评论。

下面，我添加了我的 A* 实现，PriorityQueue 只是 heapq 的包装器。

def a_star_search(mesh, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break

        for i, next in enumerate(list(mesh.neighbors(current))):
            new_cost = cost_so_far[current] + mesh.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + mesh.heuristic(next, goal) / mesh.unit
                frontier.put(next, priority)
                came_from[next] = current

    return came_from, cost_so_far

目标位于图表内时的示例结果

Answer 1

“接近”图表中没有的东西意味着是什么？如果目标节点可能出现在任何地方，那么预先计算任何内容都是没有意义的，因为在它出现后您必须重新开始。如果您知道它最终会出现在哪里，那么现在将其添加到图表中并计算您的路径，然后在(当前)已知图表的边缘截断结果。