论文标题
对具有多个边缘成本估算的图表的最短路径问题的概括
A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
论文作者
论文摘要
图中最短的路径问题是AI理论和应用的基石。现有算法通常忽略边缘重量计算时间。我们为加权的有向图提供了一个广义框架，其中可以以增加准确性和运行时费用来计算（估计）多次（估计）的边缘权重。这引发了最短路径问题的几个广义变体。我们介绍了找到最佳成本下较低距离的路径的问题。然后，我们为广义问题提供了两种完整的算法，并从经验上证明了它们的功效。
The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
