algorithm - 在隐式图中寻找最短路径时最小化连接检查的数量

Question

我很惊讶我在任何地方都找不到任何关于这个的东西，这似乎是一个应该众所周知的问题:

考虑二维欧几里得最短路径问题。给定一组障碍物多边形 P 和两个点 a 和 b，我们想要从 a 找到最短路径> 到 b 不与 P 中的任何 p(的内部)相交。

为了解决这个问题，可以为这个问题创建可见性图，该图的节点是 P 元素的顶点，如果两个节点之间的直线不相连，则两个节点相连不与 P 的任何元素相交。任何此类边的边权重就是这两点之间的欧几里得距离。为了解决这个问题，我们可以确定图中从 a 到 b 的最短路径，假设是 A*。

但是，这不是一个好的方法。预先创建可见性图需要检查任意两个多边形的任意两个顶点是否相连，这种检查比确定两个节点之间的距离复杂度更高。因此，使用 A* 的修改版本“在检查两个节点是否实际连接之前尽其所能”实际上加快了问题的速度。

仍然，A* 和所有其他最短路径问题总是从一个显式给定的图开始，对于该图，可以廉价地遍历相邻顶点。所以我的问题是，是否有一种好的(最佳？)算法可以在“隐式图”中找到两个节点 a 和 b 之间的最短路径，从而最大限度地减少检查两个节点是否已连接？

编辑:

为了阐明我的意思，这是我正在寻找的示例:

让V是一组，a , b V 的元素.假设 w: V x V -> D是一个加权函数(对于一些线性有序的集合 D )和 c: V x V -> {true, false}如果 V 有两个元素，则返回真被认为是连接的。然后下面的算法从a找到最短路径至 b在 V ，即返回列表 [x_i | i < n]这样 x_0 = a , x_{n-1} = b , 和 c(x_i, x_{i+1}) = true对于所有 i < n - 1 .

Let (V, E) be the complete graph with vertex set V.
do
    Compute shortest path from a to b in (V, E) and put it in P = [p_0, ..., p_{n-1}]
    if P = empty (there is no shortest path), return NoShortestPath
    Let all_good = true
    for i = 0 ... n - 2 do
        if c(p_i, p_{i+1}) == false, remove edge (p_i, p_{i+1}) from E, set all_good = false and exit for loop
while all_good = false

为了计算循环中的最短路径，如果存在适当的启发式算法，可以使用 A*。显然，该算法从 a 生成最短路径至 b .

另外，我想这个算法在调用 c 时是某种程度上最优的尽可能少。对于找到的最短路径，它必须排除函数 w 所包含的所有较短路径。会允许的。

但肯定有更好的方法吗？

编辑 2:

所以我找到了一个解决方案，该解决方案对于我正在尝试做的事情来说效果相对较好:使用 A*，当放宽节点时，而不是通过邻居并将它们添加到优先级队列/在优先级队列中更新它们，我把进入优先级队列的所有顶点，标记为假设的，连同假设的 f 和 g 值以及假设的父节点。然后，当从优先级队列中挑选下一个元素时，我检查是否确实给出了该节点与其父节点的连接。如果是，则节点正常进行，如果不是，则将其丢弃。

这大大减少了连接检查的次数并大大提高了我的性能。但我确信还有一种更优雅的方式，特别是“假设的新路径”不只是延长一个长度的方式( parent 总是实际的，而不是假设的)。

Answer 1

A* 或 Dijkstra 算法不需要显式图来工作，它们实际上只需要:

1. 源顶点(s)
2. 函数 next:V->2^V 满足 next(v)={u |从 v 到 u 有一条边
3. 函数 isGoal:V->{0,1} 满足 isGoal(v) = 1 当且仅当 v 是目标节点.
4. 权重函数 w:E->R 使得 w(u,v)= 从 u 移动到 v 的成本

当然，除此之外，A* 还需要一个启发式函数 h:V->R，这样 h(v) 就是成本近似值。

使用这些函数，您可以仅动态生成查找最短路径所需的图形部分。
事实上，在使用这种方法的人工智能问题中，A* 算法经常用于无限图(或不适合任何现有存储的巨大图)。

这个想法是，您只查看给定节点的 A* 中的边(对于某些给定的 u<，E 中的所有 (u,v)/)。您不需要整个边集 E 来执行此操作，您只需使用 next(u) 函数即可。