헝가리안 알고리즘_최종 채택X - 100-hours-a-week/12-marong-Wiki GitHub Wiki
📍 순환 구조 및 헝가리안 알고리즘 적용
1. 필터링 단계
- 과거 매칭 이력 존재하는 경우 매칭 제외
- 상대방과 좋아하는 음식과 싫어하는 음식이 같을 경우 후보군에서 제외
2. 비용 부여 및 비용 행렬 설정 단계
- 매칭 시기에 따라 비용을 부여하고, 궁합이 맞지 않는 MBTI일수록 추가적으로 비용 부여
3. 헝가리안 알고리즘 실행 단계
- 해당 비용 기반으로 헝가리안 알고리즘에 따른 비용의 전역적 최적화를 목표로한 1:1 매칭
4. 클러스터링을 통한 알고리즘 실행 분산 단계
시간복잡도가 O(n^3)
- 사용자가 더욱 많아지면 클러스터를 분류해서 클러스터 내에서 헝가리안 알고리즘을 적용하여 매칭을 하는 것을 고려해야 함
📍 해결 전략
- K-means, Spectral Clustering 등으로 n명의 사용자를 군집화 (30~50명 단위)
- 군집 내부에서만 헝가리안 알고리즘 적용, 주차 순환 방식으로 군집 간 교차 매칭 유도 가능 → 클러스터링을 통해 시간복잡도에 따른 문제를 완화할 수 있음
클러스터링 기준 -> 더욱 고민해야할 이슈 10,000명 기준으로 클러스터 내 인원을 200명 이하로 분할하면 단일 코어로도 충분히 해결 가능!
📍 클러스터 방식에 대한 예상 시간 시나리오
| 클러스터 수 | 클러스터당 인원수 | 연산량 (O(n³)) | 단일 코어 처리 시간 | 10코어 병렬 처리 시간 | 50코어 병렬 처리 시간 |
|---|---|---|---|---|---|
| 1 | 10,000명 | 1 × 10¹² | 10,000초 ≈ 2.8시간 | 1,000초 ≈ 16.6분 | 200초 ≈ 3.3분 |
| 10 | 1,000명 | 10 × (1 × 10⁹) = 1 × 10¹⁰ | 100초 | 10초 | 2초 |
| 50 | 200명 | 50 × (8 × 10⁶) = 4 × 10⁸ | 4초 | 0.4초 | 0.08초 |
| 100 | 100명 | 100 × (1 × 10⁶) = 1 × 10⁸ | 1초 | 0.1초 | 0.02초 |
📍 Dummy를 어디 추가하냐에 따라 Dummy와 매칭된 사람의 수행 역할 조절 가능
-
Dummy를 열(=마니띠)로 추가 → dummy와 매칭된 사람은 마니또만 수행, 마니띠 없음
-
Dummy를 행(=마니또)로 추가 → dummy와 매칭된 사람은 마니띠만 수행, 마니또 없음
❌ 채택하지 않은 이유
헝가리안 알고리즘을 사용하면 랜덤 비용의 개념을 통해 마니또 매칭의 재미를 더할 수 있음 구체적으로 각 요소별 비용 부여에서 noise를 도입하여 어떤 주에는 단순하게 성향, 좋아하는 음식, 싫어하는 음식, 취미에 따라 최적화가 이루어지지 않을 수 있는 오락적 요소를 가미할 수 있음
- 헝가리안 알고리즘도 결국엔 1:1 매칭이라 낙오자가 발생
- OR 양방향 매칭이 가능하긴 하지만 전체 유저 수가 홀수인 경우 Dummy를 추가해서 Dummy와 매칭되는 경우에는 마니또 혹은 마니띠 역할만 가능하도록