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

Question

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

为了解决target可能在图外的问题，我试过在优先级值停止变化一定时间后退出算法，但没有成功。算法吐出了一条随机路径。

我之所以没有 select 一个最接近目标的节点，是因为如果我 select 该算法肯定会尝试到达该点。在我的应用程序中，我将在新信息出现时重新运行算法（即更新可能包含目标的图表）。

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

下面，我添加了我的 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

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

Answer 2

您能否将 goal 添加到您的图形中（连接到每个其他节点，大概使用您的网格使用的任何距离度量）？或者，如果您不想修改网格数据结构，则可以循环 list(mesh.neighbors(current))+goal（在更新 new_cost = … 以处理该情况后）。

如果我误解了什么，我深表歉意，这根本不适用……

Answer 3

您可以最小化到达节点的成本加上从该节点到达目标的估计成本。一旦您知道完整的网格，就不能保证它是最佳的，但根据您的启发式，它应该是一个合理的猜测。

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

Using A* with target ouside graph

python

algorithm

heuristics

a-star