确定最大覆盖区域的算法
Algorithm for determining largest covered area
我正在寻找一种我确信一定已经研究过的算法，但我对图论不够熟悉，甚至不知道要搜索的正确术语。
在摘要中，我正在寻找一种算法来确定可达顶点 [x1, x2, xn] 和某个起始顶点之间的路由集，当每条边都有一个权重并且每条路由只能有给定的最大总重量 x.
更实际地说，我有路网，每个路段都有长度和最大行驶速度。我需要确定从网络上的任何起点在一定时间跨度内可以到达的区域。如果我能找到在那段时间内可以到达的最远点，那么我将使用凸包算法来确定面积（这对于我的用例来说已经足够了）。
所以我的问题是，如何找到这些终点？我的第一直觉是使用 Dijkstra 的算法，一旦我 'consumed' 一定的 'budget' 时间就停止，从每个路段的预算中减去；但是当算法应该回溯但已经用完预算时，我陷入困境。这个问题有已知的名称吗？
如果我对问题的理解正确，那么您的初步猜测是正确的。 Dijkstra 算法或任何其他找到从顶点到所有其他顶点（如 A*）的最短路径的算法都适合。
在最简单的情况下，您可以构建图形，其中边的权重代表通过该路段所需的最短时间。如果你知道它的长度和最大允许速度，我想你知道。 运行算法从起点开始，挑选那些最短路径小于x的顶点。就这么简单。
如果您想优化事物，请注意在 Dijkstra 算法的工作过程中，当前已知的到顶点的最短路径在每次迭代中单调增加。当您处理具有非负权重的图形时，这是一种预期。现在，在每一步中，您都选择一个具有最小当前最短路径的未使用顶点。如果这条路径大于x，你可能会停止。从现在开始，您不可能拥有任何最短路径小于 x 的顶点。
如果需要准确判断车辆在给定时间内可以到达的顶点之间的点，这只是上述算法的一个小扩展。下一步，考虑所有 (u, v) 边，其中 u 可以在时间 x 到达，而 v 不能。 IE。如果我们将到顶点 w 的最短路径定义为 t(w)，我们有 t(u) <= x 和 t(v) > x。现在使用一些基本数学在 u 和 v 之间使用系数 (x - t(u)) / (t(v) - t(u)).
插入点
从起始节点开始使用广度优先搜索似乎是解决O(V+E)时间复杂度问题的好方法。这就是 Dijkstra 所做的，但它在找到最小路径后停止。但是，在您的情况下，您必须继续为您的一组路由收集路由，直到无法扩展任何路由，使其权重小于或等于最大总权重。
而且我认为 Dijkstra 算法中没有任何回溯。
我正在寻找一种我确信一定已经研究过的算法，但我对图论不够熟悉，甚至不知道要搜索的正确术语。
在摘要中，我正在寻找一种算法来确定可达顶点 [x1, x2, xn] 和某个起始顶点之间的路由集，当每条边都有一个权重并且每条路由只能有给定的最大总重量 x.
更实际地说，我有路网，每个路段都有长度和最大行驶速度。我需要确定从网络上的任何起点在一定时间跨度内可以到达的区域。如果我能找到在那段时间内可以到达的最远点，那么我将使用凸包算法来确定面积（这对于我的用例来说已经足够了）。
所以我的问题是，如何找到这些终点？我的第一直觉是使用 Dijkstra 的算法，一旦我 'consumed' 一定的 'budget' 时间就停止，从每个路段的预算中减去；但是当算法应该回溯但已经用完预算时，我陷入困境。这个问题有已知的名称吗？
如果我对问题的理解正确，那么您的初步猜测是正确的。 Dijkstra 算法或任何其他找到从顶点到所有其他顶点（如 A*）的最短路径的算法都适合。
在最简单的情况下，您可以构建图形，其中边的权重代表通过该路段所需的最短时间。如果你知道它的长度和最大允许速度，我想你知道。 运行算法从起点开始，挑选那些最短路径小于x的顶点。就这么简单。
如果您想优化事物，请注意在 Dijkstra 算法的工作过程中，当前已知的到顶点的最短路径在每次迭代中单调增加。当您处理具有非负权重的图形时，这是一种预期。现在，在每一步中，您都选择一个具有最小当前最短路径的未使用顶点。如果这条路径大于x，你可能会停止。从现在开始，您不可能拥有任何最短路径小于 x 的顶点。
如果需要准确判断车辆在给定时间内可以到达的顶点之间的点，这只是上述算法的一个小扩展。下一步，考虑所有 (u, v) 边，其中 u 可以在时间 x 到达，而 v 不能。 IE。如果我们将到顶点 w 的最短路径定义为 t(w)，我们有 t(u) <= x 和 t(v) > x。现在使用一些基本数学在 u 和 v 之间使用系数 (x - t(u)) / (t(v) - t(u)).
从起始节点开始使用广度优先搜索似乎是解决O(V+E)时间复杂度问题的好方法。这就是 Dijkstra 所做的，但它在找到最小路径后停止。但是，在您的情况下，您必须继续为您的一组路由收集路由，直到无法扩展任何路由，使其权重小于或等于最大总权重。
而且我认为 Dijkstra 算法中没有任何回溯。