论文标题
约束最短路径和分层结构
Constrained Shortest Path and Hierarchical Structures
论文作者
论文摘要
约束最短路径（CSP）问题如下。给出了$ n $ vertex图，每个边缘/弧分配了两个权重。让我们称它们为“成本”和“长度”以确定性。需要在给定的顶点之间找到一个最小成本的上限长度路径。即使所有边缘的长度相同，问题也是NP-HARD。因此，文献中已经提出了各种近似算法。可以通过考虑一个边缘重量等于成本和长度的线性组合来考虑对路径长度的约束。通过在线性组合中改变乘数值，可行的解决方案可为新权重的功能提供最小值。同时，Dijkstra的算法或其修改用于构建具有边缘当前权重的最短路径。但是，由于图形不足，这种方法可能会很耗时。在本文中，我们建议寻找一个解决方案，而不是在原始图中，而是在特殊构建的层次结构（HS）中。我们表明，HS中最短的路径是用$ O（m）$ - 时间复杂性构建的，其中$ m $是图的边缘/弧数，并且在整数成本和边缘长度的情况下，以$ O（m \ log n）$ - 时间复杂度找到了近似解决方案。事实证明，算法准确性的先验估计取决于问题的参数，并且可能很重要。因此，为了评估该算法的有效性，我们在大型道路和随机构造的单位磁盘图（UDGS）上进行了数值实验。数值实验结果表明，在HS中，接近最佳的解决方案的构建速度比使用Dijkstra的算法在原始图中构建最小程度路径的方法快10-100倍。
The Constraint Shortest Path (CSP) problem is as follows. An $n$-vertex graph is given, each edge/arc assigned two weights. Let us call them "cost" and "length" for definiteness. Finding a min-cost upper-bounded length path between a given pair of vertices is required. The problem is NP-hard even when the lengths of all edges are the same. Therefore, various approximation algorithms have been proposed in the literature for it. The constraint on path length can be accounted for by considering one edge weight equals to a linear combination of cost and length. By varying the multiplier value in a linear combination, a feasible solution delivers a minimum to the function with new weights. At the same time, Dijkstra's algorithm or its modifications are used to construct the shortest path with the current weights of the edges. However, with insufficiently large graphs, this approach may turn out to be time-consuming. In this article, we propose to look for a solution, not in the original graph but specially constructed hierarchical structures (HS). We show that the shortest path in the HS is constructed with $O(m)$-time complexity, where $m$ is the number of edges/arcs of the graph, and the approximate solution in the case of integer costs and lengths of the edges is found with $O(m\log n)$-time complexity. The a priori estimate of the algorithm's accuracy turned out to depend on the parameters of the problem and can be significant. Therefore, to evaluate the algorithm's effectiveness, we conducted a numerical experiment on the graphs of roads of megalopolis and randomly constructed unit-disk graphs (UDGs). The numerical experiment results show that in the HS, a solution close to optimal one is built 10--100 times faster than in the methods which use Dijkstra's algorithm to build a min-weight path in the original graph.
