Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier
Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier
复制标题
通过帕累托最优前沿子集的有效表示来近似双标准搜索
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Oren Salzman
中科院分区：
文献类型：
--
作者：
Oren Salzman
我们考虑了最短路径问题，其中我们要在图表上计算最短路径，以同时平衡两个成本函数。尽管此问题有许多应用程序，但通常没有路径同时最大程度地减少两个成本功能。因此，我们通常会考虑一组路径，其中没有路径在两个成本函数中都比其他路径好，这是一个称为帕累托最佳前沿的集合。不幸的是，该集合的大小可能在图形顶点的数量中是指数的，并且一般问题是NP-HARD。尽管现有的方案近似于该集合，但在应用于相对较小的实例并在图形上运行甚至适度的节点时，它们可能比精确的方法慢。通常是不切实际的。问题的症结在于如何有效地近似帕累托最佳边界。我们的关键见解是，可以使用一对路径近似帕累托最佳边界。这种简单的观察使我们能够进行最佳的首选搜索，同时有效地修剪中间解决方案，以便在任何给定的近似因子中获得帕累托边界的近似值。我们将我们的方法与BOA*的适应方法进行了比较，BOA*是用于计算最短路径问题的精确解决方案的最新算法。我们的实验表明，随着问题变得更加困难，获得的加速变得更加明显。具体而言，在大型路线图上，当使用近似值为10％时，我们会在平均运行时间超过x19的平均运行时间获得加速。
We consider the bi-criteria shortest-path problem where we want to compute shortest paths on a graph that simultaneously balance two cost functions. While this problem has numerous applications, there is usually no path minimizing both cost functions simultaneously. Thus, we typically consider the set of paths where no path is strictly better than the others in both cost functions, a set called the Pareto-optimal frontier. Unfortunately, the size of this set may be exponential in the number of graph vertices and the general problem is NP-hard. While existing schemes to approximate this set exist, they may be slower than exact approaches when applied to relatively small instances and running them on graphs with even a moderate number of nodes is often impractical. The crux of the problem lies in how to efficiently approximate the Pareto-optimal frontier. Our key insight is that the Pareto-optimal frontier can be approximated using pairs of paths. This simple observation allows us to run a best-first-search while efficiently and effectively pruning away intermediate solutions in order to obtain an approximation of the Pareto frontier for any given approximation factor. We compared our approach with an adaptation of BOA*, the state-of-the-art algorithm for computing exact solutions to the bi-criteria shortest-path problem. Our experiments show that as the problem becomes harder, the speedup obtained becomes more pronounced. Specifically, on large roadmaps, when using an approximation factor of 10% we obtain a speedup on the average running time of more than X19.
一种简单快速的双目标搜索算法
DOI：
--
发表时间：
2020
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
--
作者：
Hernandez, C.;Yeoh, W.;Baier, J.;Zhang, H.;Suazo, L.;Koenig, S.
通讯作者：
Koenig, S.