OR Tools ‐ Google PATH_CHEAPEST_ARC 방식 - 100-hours-a-week/12-marong-Wiki GitHub Wiki

📍 OR Tools - Google PATH_CHEAPEST_ARC 방식

시작 노드를 정해서 해당 노드에 대해 Greedy한 방식으로 경로를 연결하여 마니또-마니띠 매칭에서 원형 매칭 방식을 구현하고자 함

✔️ 채택 이유

  • 헝가리안 알고리즘, Blossom 알고리즘은 짝수인 경우에만 완전 매칭이 가능하며, 홀수 유저의 경우 마니또 혹은 마니띠 역할만 가능하거나 운영진이 개입해야 하는 문제가 발생함.
  • 시작 노드와, 중간 노드, 종료 노드가 있을 때 종료 노드가 시작 노드와 일방향 매칭(종료 노드의 마니띠가 시작 노드가 되는 경우)이 되는 조건이 만족되면, 홀수의 경우에도 마니또-마니띠 완전 매칭이 가능함
  • 다만 매칭 구조를 설계한다고 할 때 BRUTE FORCE 방식(모든 순열의 경우 도출)으로 매칭을 진행하면 최적해는 보장되나 시간복잡도가 O(n!)이므로 20명 이상인 경우 현실적으로 해당 방식으로 매칭하기는 어려움
  • 따라서 Greedy한 방식으로 매칭하되, 근사 최적해를 구할 수 있는 매칭 방식인 PATH_CHEAPEST_ARC 방식을 채택

📍 수학적 정의

PATH_CHEAPEST_ARC는 **외판원 순회 문제(TSP)**의 초기 해를 구하는 탐욕적 알고리즘으로 정의되며, 다음 수식으로 표현된다

✔️ 알고리즘 정의

  • 주어진 집합: $V = {v_1, v_2, \dots, v_n}$ (참가자 집합)
  • 비용 행렬: $C = [c_{ij}]$, $c_{ij}$는 $v_i$에서 $v_j$로 가는 비용 (작을수록 궁합이 좋음)

✔️ 알고리즘 흐름

  1. 시작 노드 $v_s$ 선택

  2. 현재 노드 $v_{\text{cur}}$에서 아직 방문하지 않은 노드 중 최소 비용 $c_{ij}$를 가지는 $v_j$ 선택: $v_{\text{next}} = \arg\min_{j \in V_{\text{unvisited}}} c_{v_{\text{cur}}, j}$

  3. $v_{\text{cur}} \to v_{\text{next}}$로 이동하고, $v_{\text{next}}$를 방문 처리

  4. 모든 노드를 방문할 때까지 반복

  5. 마지막 노드에서 시작 노드로 돌아가는 경로 추가하여 순환 경로 구성

✔️ 시간 복잡도

  • Greedy 방식이므로 $O(n^2)$

📍 실제 적용 예시: 마니또 원형 매칭

참가자 수: 5명

A B C D E
A ∞ 2 9 10 7
B 1 ∞ 6 4 3
C 15 7 ∞ 8 12
D 6 3 12 ∞ 5
E 8 6 5 7 ∞

순환 경로 결과

A → B → E → C → D → A
총 비용: 2 + 3 + 5 + 8 + 6 = 24

📍 개선 전략

1. 비용 제한 (Cost Threshold) 적용

  • 특정 $c_{ij} > \text{Threshold}$ 인 경우 연결 차단
  • MBTI 궁합, 취미 등을 기준으로 조합 필터링

2. 제약 완화 반복 (Constraint Relaxation Loop)

  • 초기엔 제한된 비용만 허용 → 경로 탐색 실패 시 점차 비용 허용 범위 확장
  • 예: 50 → 60 → 70 … 100까지

3. Local Search (국소 최적화) 결합

  • 초기 탐욕 해에서 시작해, 인접 경로 스왑 등을 통해 총 비용을 감소시킴
  • Google OR-Tools에서는 Guided Local Search, Simulated Annealing, Tabu Search 등 지원

4. Soft Constraint 기반 비용 설계

  • MBTI, 취미, 선호 음식 등을 가중치 기반 비용 함수로 변환하여 cost[i][j]로 사용
  • 다중 요소를 반영한 유사도 기반 최적화 가능

📍 요약

항목 설명
알고리즘 PATH_CHEAPEST_ARC (탐욕적 순차 연결)
특성 O(n²), 순환 경로, 빠름
장점 빠르고 원형 구조에 적합, 홀수 매칭 가능
단점 전역 최적 보장 X (보완 필요)
개선법 비용 제한, 제약 완화, Local Search, 가중치 설계 등
  • 최소 3인 이상은 필요!