algorithm - 在隐式图中查找最短路径时，最大程度地减少连接检查的次数

我很惊讶我在这上面找不到任何东西，这似乎是一个众所周知的问题：
考虑二维欧氏最短路径问题。给定一组障碍多边形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值和假设的父值。然后，当从优先级队列中选择下一个元素时，我检查节点与其父节点的连接是否实际给定。如果是，则节点按正常方式进行，如果不是，则丢弃该节点。
这大大减少了连接检查的次数，并大大提高了我的性能。但我相信还有一种更优雅的方式，特别是“假想的新路”不仅仅是延伸一段（父母总是实际的，而不是假想的）。

最佳答案

A*或Dijkstra的算法不需要显式的图，它们实际上只需要：
源顶点（s）
一个函数，使得
使iff是目标节点的函数。
权重函数next:V->2^V使得w（u，v）=从u移动到v的成本
当然，此外，A*需要一个启发式函数next(v)={u | there is an edge from v to u }，这样isGoal:V->{0,1}是代价近似。
使用这些函数，您只能动态地生成图中查找最短路径所需的部分。
事实上，A*算法经常使用在无限图（或不适用于任何现有存储的巨大图）的人工智能问题中。
其思想是，您只查看来自给定节点的*中的边（对于某些给定节点，所有边都isGoal(v) = 1在v中）。不需要将整个边集w:E->R设置为这样做，只需使用h:V->R函数即可。

关于algorithm - 在隐式图中查找最短路径时，最大程度地减少连接检查的次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23561134/