确定覆盖面积最大的算法

Question

我正在寻找一个算法，我确信这个算法已经被研究过，但是我对图论不熟悉，甚至不知道搜索正确的术语。

简单来说，我正在寻找一种算法，以确定在每条边有权重且每个路线仅能具有给定的最大总权重x的情况下，可到达顶点[x1、x2、xn]和某个起始顶点之间的路线集。

更实际地说，我有一个道路网络，每个道路段都有长度和最大行驶速度。我需要确定可以从网络上任何起点内一定时间范围内到达的区域。如果我可以找到在该时间范围内可到达的最远点，则将使用凸包算法确定该区域（这足以适用于我的用例）。

所以我的问题是，如何找到那些最终点？我的第一反应是使用Dijkstra算法，并在“消耗”一定的时间预算后停止，每个道路段减去预算；但当算法需要回溯但已用尽预算时，我就卡住了。是否有已知名称的此问题？

- Roel

---

你正在查看最大流问题。你是想要它的名称还是大致分析？ - Makoto

请查看https://en.wikipedia.org/wiki/Maximum_coverage_problem和相关问题https://dev59.com/51DTa4cB1Zd3GeqPNOvL。 - Mihai8

@Makoto 是吗？据我所知，最大流仅用于查找从给定源到给定目的地的一条路径，并具有最大的“吞吐量”？ - Roel

@user1929959 我不确定那与我的问题有什么关系 - 我并不在意访问尽可能多的链接，我只想要从一个给定点获得最大距离。但我可能只是没有看到它们之间的联系。 - Roel

Answer 1

如果我正确理解了您的问题，那么您的初始猜测是正确的。Dijkstra算法或任何其他从一个顶点到所有其他顶点寻找最短路径的算法（如A *）都适用。

在最简单的情况下，您可以构造图形，其中边的权重表示通过这段道路所需的最小时间。如果您知道其长度和允许的最大速度，我假设您已经知道它。从起点运行算法，选择那些最短路径小于“x”的顶点。就这么简单。

如果您想要优化事情，请注意，在Dijkstra算法的工作期间，当前已知的到达各个顶点的最短路径会随每次迭代单调递增。当您处理具有非负权重的图表时，这是预期的。现在，在每个步骤中，您都会选择具有最小当前最短路径的未使用顶点。如果此路径大于“x”，则可以停止。从现在开始，您不可能拥有任何最短路径小于“x”的顶点。

如果您需要精确确定车辆在给定时间内可以到达的顶点之间的点，则只需对上述算法进行小型扩展。接下来，考虑所有u，v边缘，其中u可以在时间x内到达，而v不能。即如果我们将到达顶点w的最短路径定义为，则我们具有<=x>和>x。现在使用一些基本数学来以系数<(x-t(u))/(t(v)-t(u))>在u和之间插值点。

- Mikhail

---

谢谢，这个答案（加上@div的）让我找到了正确的方向。当我将问题重新表述为“找到所有距离给定起始点v1不超过预算x的点”时，我没能意识到的事情变得显而易见了。我会让Dijkstra在整个图上运行，不是在到达给定终点时停止，而是在超出预算时停止。此时，我图中所有访问过的顶点的预算都低于x，然后我的凸包算法就会剔除边界内的所有点。（续...） - Roel

这样做甚至可以涵盖一些病态情况，即路径中后面的顶点更靠近起始节点（因为道路绕过障碍物或湖泊），这将使我的“覆盖区域”比所需的小。当然，这正是你说的，但直到我用上面写的方式表达出来，我才恍然大悟 :) - Roel

Answer 2

从起始节点使用广度优先搜索似乎是以O(V+E)的时间复杂度解决问题的好方法。这就是Dijkstra所做的，但它在找到最短路径后停止。然而，在您的情况下，您必须继续收集路径直到没有路径可以扩展，使其权重小于或等于最大总权重。

我不认为Dijkstra算法中有任何回溯。

- div

---

谢谢。你说得对，我关于回溯的评论是因为我对我们已经使用的修改版Dijkstra算法的误解，对于造成的混淆感到抱歉。 - Roel