핵심 아이디어는 "문제를 통째로 풀지 말고 쪼개자"예요

NP-하드 문제인 최소 집합 커버를 더 빠르게 푸는 방법이 논문으로 나왔어요.

핵심 아이디어는 "문제를 통째로 풀지 말고 쪼개자"예요. 원소들이 서브셋 안에서 함께 등장하는 패턴을 분석하면, 전체 문제가 독립적인 작은 부분 문제들로 분리된다는 거예요. 이 구조를 Union-Find 알고리즘으로 전처리 단계에서 감지해요.

각 부분 문제는 GRASP 메타휴리스틱으로 따로 풀고, 결과를 합쳐도 해의 타당성이 깨지지 않아요. 여기에 비트 단위 집합 표현을 써서 연산 효율도 높였고, 대규모 벤치마크에서 품질과 확장성 모두 개선됐다고 보고했어요.

구조적으로 분해 가능한 인스턴스일수록 이득이 크다는 점이 흥미로운데, 현실 문제 상당수가 이런 숨겨진 구조를 갖고 있다는 걸 시사해요.