최대 쌍 수 계산 알고리즘

Question

남성과 여성 모두를 포함하는 두 개의 테이블이 있습니다. 나이, 인종 및 관심사 (각 변수에 대해 예 또는 아니요)를 알고 있습니다. 목표는 쌍을 조합하여 쌍의 최대 수를 설정하는 것입니다.

페어링에 대한 몇 가지 기준이있다

:

• 이들의 연령은 +해야 -
• 같은 인종 처음 3 년 만 차이 경주는
• 그들은 공통의 관심사
의 최대 수 있어야한다 허용

루프의 여러 레이어를 만드는 대신 다른 조건이 있으면이 프로세스의 속도를 높이는 알고리즘이 더 빠릅니까?

Answer 1

먼저 해당 기준에 따라 남성과 여성의 우선 순위를 설정 한 다음 Stable marriage problem 알고리즘을 적용하여 가능한 최대 페어링을 만듭니다.

각 남성의 경우 위의 기준에 따라 별개의 정렬 목록 (기본 설정 목록)을 만들고 여성의 경우 그 반대의 경우도 마찬가지입니다. 이것은 사용자 정의 비교기로 수와 암 배열을 여러 번 정렬하는 것입니다.

이제 남성과 여성 각각에 대한 기본 설정 목록이 있습니다. 안정된 결혼 알고리즘을 실행할 준비가되었습니다. 최대 쌍을 얻을 수 있습니다. 안정적인 결혼 문제의 일반적인 의사 코드는 다음과 같습니다 제대로 알고리즘을 구현하는 경우, 시간 복잡도는 최악의 경우 평균 경우에 O(nlogn) 및 O(n^2) 될 것

function stableMatching { 
    Initialize all m ∈ M and w ∈ W to free 
    while ∃ free man m who still has a woman w to propose to { 
     w = first woman on m’s list to whom m has not yet proposed 
     if w is free 
     (m, w) become engaged 
     else some pair (m', w) already exists 
     if w prefers m to m' 
      m' becomes free 
      (m, w) become engaged 
     else 
      (m', w) remain engaged 
    } 
} 

.