Parallel Label-Setting Multi-objective Shortest Path Search
Parallel Label-Setting Multi-objective Shortest Path Search
复制标题
并行标签设置多目标最短路径搜索
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Mandow
中科院分区：
文献类型：
--
作者：
P. Sanders;L. Mandow
我们提出了一种用于从图中指定的源的所有Pareto最佳路径的并行算法。一个到多个目标是完全可行的。算法。我们还讨论了D≥3个目标函数和单个目标搜索的概括。
We present a parallel algorithm for finding all Pareto optimal paths from a specified source in a graph. The algorithm is label-setting, i.e., it only performs work on distance labels that are optimal. The main result is that the added complexity when going from one to multiple objectives is completely parallelizable. The algorithm is based on a multiobjective generalization of a priority queue. Such a Pareto queue can be efficiently implemented for two dimensions. Surprisingly, the parallel biobjective approach yields an algorithm performing asymptotically less work than the previous sequential algorithms. We also discuss generalizations for d ≥ 3 objective functions and for single target search.