首页 文章

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

提问于
浏览 次
0

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

从二维考虑欧几里德最短路径问题 . 给定一组障碍多边形P和两个点a和b，我们希望找到从a到b的最短路径不与P中任何p的（内部）相交 .

为了解决这个问题，可以为这个问题创建可见性图，其中节点是P元素顶点的图，如果两个节点之间的直线不与P的任何元素相交，则连接两个节点 . 边缘权重任何这样的边缘都只是这两点之间的欧几里德距离 . 为了解决这个问题，我们可以确定图中a到b的最短路径，比方说A * .

但是，这不是一个好方法 . 事先创建可见性图表需要检查是否连接了任何两个多边形中的任何两个顶点，这一检查的复杂性高于确定两个节点之间的距离 . 因此，使用A *的修改版本“在检查两个节点是否实际连接之前做了所有事情”实际上加速了问题 .

仍然，A *和所有其他最短路径问题始终以明确给定的图形开始，对于该图形，可以廉价地遍历相邻的顶点 . 所以我的问题是，是否有一个好的（最优？）算法，用于在“隐式图”中找到两个节点a和b之间的最短路径，最小化检查两个节点是否连接？

Edit:

为了澄清我的意思，这是我正在寻找的一个例子：

设 V 是 V 的集合， a ， b 元素 . 假设 w: V x V -> D 是称重函数（对某些线性排序的集合 D ），如果认为 V 的两个元素被连接，则 c: V x V -> {true, false} 返回true . 然后，以下算法在 V 中找到从 a 到 b 的最短路径，即返回列表 [x_i | i < n] ，使得所有 i < n - 1 的 x_0 = a ， x_{n-1} = b 和 c(x_i, x_{i+1}) = true .

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 允许的所有较短路径 .

但肯定有更好的方法吗？

Edit 2:

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

这大大减少了连接检查的数量，并为我提高了很多性能 . 但我确信仍然有一种更优雅的方式，特别是“假设的新路径”不仅仅延伸一长度（父母总是实际的，而不是假设的） .

algorithm graph-theory shortest-path

1 回答

  • 2

    A *或Dijkstra的算法不需要显式图，它们实际上只需要：

    • 源顶点（ s ）

    • 一个函数 next:V->2^V 这样 next(v)={u | there is an edge from v to u }

    • 函数 isGoal:V->{0,1} ，使 isGoal(v) = 1 iff v 是目标节点 .

    • 权重函数 w:E->R 使得w（u，v）=从u移动到v的成本

    而且，当然，另外A *需要一个启发式函数 h:V->R ，这样 h(v) 就是成本近似值 .

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

    这个想法是，你只看到来自给定节点的A *中的边（对于某些给定的 u ，所有 (u,v) 在 E 中） . 您不需要设置整个边缘 E 来执行此操作，您只需使用 next(u) 函数即可 .

    回复于

相关问题