Approximate multi-objective search

Han Zhang

doi:10.1016/j.artint.2026.104542

Approximate multi-objective search

2026-04-25

0

PRE

AI

DOI：10.1016/j.artint.2026.104542

原文链接

原文求助

摘要

En 中文

在多目标搜索中，我们考虑一个图，其边被标注了多个成本分量。一个典型任务是计算帕累托前沿，即从给定起始状态到给定目标状态的所有非支配路径的集合。然而，帕累托前沿的大小可能是图规模的指数级，计算整个帕累托前沿可能非常耗时。因此，本文研究了如何为用户提供的一个近似因子寻找近似前沿。这种前沿可以远小于帕累托前沿，从而能够设计高效的近似多目标搜索算法。我们提出了一种名为A*pex的算法，它利用一种高效但近似的路径表示方法（针对成本相近的路径）来计算近似前沿。在搜索过程中，它避免了显式存储所有路径，从而减少了搜索工作量。我们展示了A*pex可以作为算法构建块用于解决其他问题：通过提出（1）A*pex的 anytime 变体，该变体快速计算初始近似前沿，然后努力寻找更好的近似前沿，直至最终找到整个帕累托前沿；（2）A*pex的变体用于近似求解权值约束最短路径（WCSP）问题，该问题与多目标搜索密切相关。为进行评估，我们使用第9届DIMACS实现挑战赛：最短路径中的道路网络进行测试。实验结果表明，A*pex及其WCSP变体在运行时间方面可以比各自的最优算法快一个数量级以上。我们还展示了A*pex的 anytime 变体在有限运行时间内通常能计算比最优算法更好的近似前沿。

Approximate multi-objective search

摘要

期刊

机构

引用论文