logo标签列表

动态变化距离的图中最短路径？（最大能量路径）

algorithmgraphgraph-theorylandscape
10

我正在尝试在离散能源地形图上找到两个极大值之间最短的路径，其中最短路径是指其在整个路径过程中高度下降最少的路径。也许最大能量路径更正确，但换句话说，即使路径绕着地形图走了很长的距离，但没有进入山谷，这也被认为是好的。

我的初始想法是创建一个地形图的图形，其中权重是相邻之间地形高度差异，上升和下降分别为正和负。我刚意识到，这将不能给出我需要的结果，实际上在本地极大值之间的所有路径将具有完全相同的成本。

然后我意识到，如果此图上节点之间的距离取决于路径的当前位置和历史记录，那么我可以得到所需的结果。例如，如果路径从一个山谷下降并上升，那么我不会对进入另一个山谷（只要路径没有超过它以前未曾去过的低点）额外收费。

那么是否存在动态更改距离的图搜索算法？

或者是否有其他攻击该问题的建议？

你特别提到了山谷，那么山峰呢？比如说一条路先上坡后下坡，这种“下降”也被认为是不好的吗？如果是的话，我赞同Eiko的想法。如果不是，我会再考虑一下 ;) - Nicolas78
一条路径可以向下或向上（当然也可以绕路），但由于我正在寻找局部极大值（或山峰）之间的路径，因此根据定义，路径必须在某个点下降。它必须下降到达目标最大值的程度可以被认为是路径的代价，我试图将其最小化。 - zenna
请问这个图的拓扑结构有什么假设吗？最好是一个（好的）矩形网格吗？我还不确定它会如何帮助，但这可能是有用的。 - Bolo
不，实际上它是一个由几百个甚至几千个维度组成的组合景观。 - zenna
6个回答
7
这被称为瓶颈最短路径问题。实际上比最短路径问题更容易，在无向图上可以在线性时间内解决。例如，可以查看这里。
谢谢。我一直在研究这篇论文，但我无法理解他们如何修改权重以使每个权重都是唯一的，并确保找到最短路径。 - zenna
@zenna：你只需要在确保不干扰其他排序的情况下，确定所有标记相同的边的唯一排序。例如，如果您有整数权重和3条权重为10的边，请将它们替换为10.1、10.2和10.3。那么显然对于任何路径，在更改前后瓶颈边都是相同的。 - Falk Hüffner
谢谢！我已经在Python中实现了一个版本（尚未考虑相等权重）http://pastebin.com/JKcMuWAn。我还有一个问题：论文指出容量（或边缘权重）必须是整数。我不明白连续数字如何影响此算法。如果确实是限制，我是否可以将当前范围（-1到1）简单地缩放到整数范围（0到整数MAX）？ - zenna
@FalkHüffner 链接已过期，有人可以提供同一来源的最新链接吗？ - manifold
2

思路

我建议使用一种算法来构建一个辅助树（T），其中每个节点包含一个顶点列表。每个子树将包含一组由山谷与其余图形分开的顶点。要找到任何两个节点之间的距离，只需在树中找到它们的最近公共祖先。

算法

初始化：

  1. 按高度升序排列顶点（空间：O(V)，时间：O(V log V)）
  2. 让T仅包含根节点r

MakeTree(G, r)：

  1. 从图形G中取出最低的顶点，将其从图形中删除并添加到根r中的列表中（每个顶点的时间成本：O(1 + E/V)）
  2. 只要图形连接，就重复上述步骤
  3. 对于图形G的每个连接组件G'：
    1. 在T中创建一个新节点n，将该节点附加为根的子节点
    2. 递归运行MakeTree(G', n)

现在，您已经拥有了这样一棵树，如果要从顶点A到B，则您的最大能量路径将通过存储在A和B的最近公共祖先中的最高顶点。为了找到距离，只需找到最近的公共祖先并获取存储在那里的最高顶点C，然后计算max(abs(h(A) - h(C)), abs(h(B) - h(C)))。

示例

下面是一个示例图形及其对应的树（为简洁起见，顶点标签是它们的高度）。例如，如果要从22到14，则必须通过10（存储在树中最近公共祖先中的最高顶点，距离=22-10）。

                                    Example

1
也许以下方法可行：
用距离加上高度差的绝对值作为权重创建地形图。
绝对值函数使得上升或下降变得昂贵，正如你已经注意到的那样，仅有高度差是不够的，因为无论你选择哪条路线，高度差都是相同的。
距离是平面距离（甚至在所有情况下都是常数1），可以省略，但如果你想要获得短路径，这应该会优先考虑成本相同的短路径而非长路径。
当然，这还没有经过测试。 :-)
谢谢。嗯，我想我有点混淆了，也许应该重新表述一下。我不关心路径在景观周围的距离有多远，我只想要能量消耗最少的路径。如果我们只考虑绝对差异，那么上下小颠簸会花费很多成本，这是不应该的。另一方面，如果我们只计算下降，那么每个山谷我们就要付出双倍的代价（如果这有任何意义的话）。 - zenna
上下移动1个单位100次比一次移动100个单位的能量消耗更大，这是为什么？从物理上讲，工作应该是相等的。如果不是，请相应地调整您的权重模型。 - Eiko
实际上，上下移动100次不应该消耗更多的能量。但是，如果我们使用绝对差，你将会在路径上每走一步都要添加dist+(1)，除非我误解了你的意思。 - zenna
是的，正如我所说：它只是为了减少步骤，你应该随意省略它 - 这很容易破坏整个算法。 - Eiko
当然你可以省略dist，但我的意思是abs()内部的术语本身会导致额外的能量消耗。如果你不是指省略abs(h_a - h_b)，那还剩下什么？ - zenna
显示剩余3条评论
1

假设端点在极大值处，您的问题等同于以下问题：

对于图中的x，让h(x)为起点下方的距离。（根据问题的陈述，所有点都在起点下方）。

找到最小化max(h(x) for x in path)的路径。

您可以使用Dijkstra最短路径的变体来解决此问题。我已经从维基百科复制并修改了算法的描述（只有第3步中的距离计算发生了变化）。

  1. 为每个节点分配一个距离值。将初始节点的距离设置为零，所有其他节点的距离设置为无穷大。

  2. 将所有节点标记为未访问。将初始节点设为当前节点。

  3. 对于当前节点，考虑其所有未访问的邻居，并计算它们到初始节点的临时距离。例如，如果当前节点（A）的距离为6，并且连接到另一个节点（B），h(B) = 7，则通过A到B的距离将是max（6,7）= 7。如果此距离小于先前记录的距离（在开始时为无穷大，在初始节点处为零），则覆盖该距离。

  4. 当考虑完当前节点的所有邻居后，将其标记为已访问。已访问的节点将不会再次被检查；现在记录的距离是最终且最小的。如果所有节点都已访问完，则结束。否则，将具有从初始节点到达的最小距离的未访问节点设置为下一个“当前节点”，并从步骤3继续。

实际上，应该最大化 min(h(x) for x in path)。 - Martijn
这看起来很有前途，在我制作的一个小文本中已经起作用了，我相信它是最大值而不是最小值。到目前为止我遇到的问题是，我无法像标准的Dijkstra算法那样在找到目标后提前停止。我会回报的。 - zenna
@Martijn 我仍然认为我写的是正确的。min(h(x) for x in path)总是0（因为起始点的h(x)=0）。 - user97370
我认为这只是对h符号的混淆。我原以为你的意思是如果x低于最大值，h(x)将为负数，但如果你改变符号，你的表述当然是正确的。 - Martijn
1

所以你完全不关心总路径长度，对吧？只关心沿途遇到的最小值？

如果是这样的话，那么你在 Dijkstra 中不应该使用传统意义上的“距离”作为成本。你的优先队列应该返回能量值最高的节点 - 这样你就保证永远不会走一条低价值的路径，如果存在更好的路径。

我认为这与 @Paul Hankin 在他的答案中提出的不同。这可能会打开图中许多节点；我认为你可以进行以下优化：

  1. 在比较函数中使用[欧几里得距离或曼哈顿距离]作为决定胜负的关键因素。这样，如果两个节点的能量相等，你会选择那个更快到达目标的节点。

  2. 将节点添加到优先队列时，不要使用其实际能量作为“成本”，而是使用其能量和迄今为止遇到的最小能量中的最小值。由于你只关心全局最小成本，一旦你被迫选择一个低能量节点，高于该成本的所有节点都“花费”相同。这使搜索在目标附近的行为类似于正常的A*搜索。

  3. 从局部最大值较低的位置开始搜索（我不确定，但我认为这样会更快）。

在#1中使用距离作为决胜者不会影响最小能量，但应该可以使搜索运行更快（有点像A*搜索）。

编辑：这里有一种完全不同（但可能更慢）的思考方式。

首先，选择一个阈值能量。进行标准的Dijkstra / A *搜索，但拒绝任何能量低于阈值的节点。如果没有路径，请选择更大的阈值再次尝试。一个“安全”的初始猜测是从起点到目标沿着简单路径（例如向左然后向上走）的最小E。

现在增加阈值，并重新执行Dijkstra / A *。一直这样做，直到找不到路径为止。在找不到路径之前的最后一条路径是具有最大最小能量的最短路径。

您还可以将一个搜索的路径成本作为下一个搜索的改进A *启发式重复使用。由于增加阈值只会增加路径长度，因此它是可接受的启发式。

希望这有所帮助。如果有任何不清楚的地方，请告诉我。
点2并不是十分清晰：您应该使用“到达一个节点的最小能量”，称为E。连接一个节点到已经访问过的节点的“代价”是它自身能量和前一个节点处E值之间的最小值。 - Martijn
@Martijn - 我不同意（如果我在回答开始时的假设是正确的）。考虑搜索经过“低谷”并接近目标后的状态。由于所有靠近目标的节点都大于低谷处的值，因此每个节点的有效成本为零，因为它们中的任何一个都不会沿着路径减少全局最小值。 - celion
没错。这就是你将非本地量定义为路径长度的结果 :)。 - Martijn
0

有两种可能性。

a) 在例如http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm版本中，有一行代码可以通过经过点u的路径计算出到点v的可能改进距离：

alt := dist[u] + dist_between(u, v)

14 if alt < dist[v]: // Relax (u,v,a)

15 dist[v] := alt

16 previous[v] := u

您似乎想要一个版本，它使用alt := K - min(height[u], height[v])。这个版本之所以有效，原因与加法版本相同：在任何时候，从源头到任何路线的所有顶点集合都正确地计算出了最小成本。每次从Q中删除一个顶点时，因为您正在删除具有最小距离的顶点，所以没有机会使用仍然在Q中的其他顶点对其进行任何捷径。

第二步：采用任何一种方法来确定是否存在从源点到目标点的路径。使用一个仅包含高度>=H的点的图形，并查看是否有解决方案。尝试不同的H值，直到找到一个可行的解决方案。您可以预先对所有高度进行排序，然后在此数组上使用二分法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接