다목적 최단경로(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배 이상 속도 향상을 보였다.
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search
- 1.다목적 최단경로에 다중값 휴리스틱(MVH)과 차원축소(DR)를 안전 결합한 첫 이론 프레임워크 제시
- 2.단순 결합 시 DR의 정렬 불변성이 깨져 탐색이 부정확·불완전해지는 문제 규명
- 3.L-NAMOA*dr-mvh는 지연·낙관적 DR로 국소 정렬 위반을 동적 복구해 정확성 유지
- 4.벤치마크서 최첨단 대비 동등 이상, 일부 사례서 10배 이상 속도 향상
왜 중요한가?
MVH의 강한 가지치기를 차원축소와 결합하지 못하던 한계를 풀어, 경로계획·물류 등 다목적 탐색 응용에서 정확성을 유지하며 실질적 속도 개선을 가능케 한다.
언급 프로젝트
다중 목표 탐색에서 다치(Multi-Valued) 휴리스틱과 차원 축소 기법을 연결하는 연구 논문입니다. 복잡한 의사 결정 문제나 최적화가 필요한 국내 인공지능 연구기관 및 기업에게 더욱 효율적인 알고리즘 설계와 성능 향상에 대한 이론적 기반을 제공할 수 있습니다.
본문 미리보기
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
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 13:55AI 초안
