다목적 최단경로(MOSP) 알고리즘은 보통 각 상태에 단일 비용 벡터를 대응시키는 단일값 휴리스틱(SVH)에 의존하는데, 이는 안전한 하한을 주지만 파레토 프론티어의 절충 구조를 못 담아 탐색 안내가 약하다. 다값 휴리스틱(MVH)은 상태를 비용 추정 집합에 대응시켜 절충을 풍부하게 근사하지만, 차원 축소(DR)와 결합하면 DR이 요구하는 순서 불변식을 깨뜨려 비건전·불완전 탐색을 낳는다. 저자는 MVH와 DR을 안전하게 통합하는 첫 이론 틀을 제시하며, 휴리스틱 일관성을 강제하는 이론적 베이스라인 NAMOA*_dr-mvh와, 게으른 낙관적 DR로 지역 순서 위반을 동적으로 탐지·복구하는 L-NAMOA*_dr-mvh를 도입한다. 후자는 다양한 벤치마크에서 최신 알고리즘과 동등하거나 우수하며 최대 10배 이상 속도 향상을 보였다.
- •다값 휴리스틱(MVH)을 차원 축소(DR)와 결합하면 순서 불변식이 깨져 비건전·불완전 탐색이 됨을 보였다.
- •MVH와 DR을 안전하게 통합하는 첫 이론 틀을 제시한다.
- •휴리스틱 일관성을 강제하는 NAMOA*_dr-mvh와 게으른 낙관적 DR 기반 L-NAMOA*_dr-mvh를 도입한다.
- •L-NAMOA*_dr-mvh는 최신 알고리즘과 동등·우수하며 최대 10배 이상 속도 향상을 보였다.
Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search
본문 미리보기
arXiv:2606.20644v1 Announce Type: new Abstract: Multi-objective shortest-path (MOSP) algorithms traditionally rely on single-valued heuristics (SVHs), which associate each state with a single admissible cost vector. While SVHs provide safe lower bounds, they fail to capture the trade-off structure of the Pareto frontier and often yield weak search guidance. Multi-valued heuristics (MVHs) address this limitation by mapping states to sets of cost estimates, enabling a richer approximation of poss
전체 내용이 궁금하다면?
원문을 직접 읽어보세요