Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
Created by
Haebom
저자
Aniss Aiman Medbouhi, Alejandro Garcia-Castellanos, Giovanni Luca Marchetti, Daniel Pelt, Erik J Bekkers, Danica Kragic
개요
쌍곡 공간에서 Steiner Minimal Trees (SMT) 구성 문제를 연구한다. 정확한 SMT 계산은 NP-hard이며, HyperSteiner와 같은 기존 쌍곡선 휴리스틱은 결정론적이며 종종 지역적으로 최적화되지 않은 구성에 갇힌다. 무작위성을 확장 과정에 통합하고 Riemannian gradient descent 최적화를 통해 후보 트리를 개선하는 확률적 Delaunay 삼각 측량 휴리스틱인 Randomized HyperSteiner (RHS)를 소개한다. 합성 데이터 세트 및 실제 단일 세포 전사체 데이터에 대한 실험 결과, RHS는 Minimum Spanning Tree (MST), Neighbor Joining 및 vanilla HyperSteiner (HS)보다 우수하다는 것을 보여준다. 경계 근처 구성에서 RHS는 HS에 비해 총 길이에서 32% 감소를 달성하여 다양한 데이터 환경에서 효과와 견고성을 입증한다.