본 논문은 다양한 규모와 분포에서 신경망 기반 여행판매원 문제(TSP) 풀이 알고리즘의 일반화 문제를 해결하기 위한 연구를 다룹니다. 기존 신경망 기반 접근법은 다양한 문제 인스턴스에서 보편적인 패턴을 식별하고 최적 해를 도출하는 데 어려움을 겪는다는 점에 착안하여, 연구진은 최적 TSP 해의 근본적인 구조적 원리인 순수성 법칙(Purity Law, PuLa)을 발견했습니다. PuLa는 가장자리의 출현 빈도가 주변 정점의 희소성에 따라 기하급수적으로 증가한다는 것을 정의하며, 다양한 인스턴스에서 통계적으로 검증되었습니다. 이러한 통찰력을 바탕으로, 본 논문은 신경망 기반 해의 특성을 PuLa와 명시적으로 정렬하여 일반화 성능을 향상시키는 새로운 훈련 패러다임인 순수성 정책 최적화(Purity Policy Optimization, PUPO)를 제안합니다. 광범위한 실험을 통해 PUPO가 기존 신경망 풀이기에 손쉽게 통합될 수 있으며, 추론 시 추가적인 계산 비용 없이 일반화 성능을 크게 향상시킨다는 것을 보여줍니다.
