最大ペア数の計算アルゴリズム

Question

男性と女性の両方を含む2つのテーブルがあります。私は年齢、人種、興味を知っています（変数ごとにはい、いいえ）。目的はそれらをペアにしてペアの最大数を設定することです。

ペアリングのためのいくつかの基準があります：

• は、彼らの年齢は+でなければなりません - 最初と同じレース3年
• 、その差のレースは、彼らが共通の利益の最大数を持っている必要があり
• 許容され

ループのレイヤーをたくさん作成するのではなく、条件が他の場合は、このプロセスを高速化するアルゴリズムがありますか？

Answer 1

まず、これらの基準に従って男性と女性の優先順位を設定し、Stable marriage problemアルゴリズムを適用して、最大のペアリングを可能にします。

各男性については、上記の基準に従って別のソート済みリスト（優先リスト）を作成し、その逆も同様です。これはカスタムコンパレータで男性と女性の配列を何度もソートすることです。

今、男性と女性のそれぞれについて優先リストを用意していますので、最大限のペアを得るために安定した結婚アルゴリズムを実行する準備は整っています。安定結婚問題の共通の擬似コードは次のようになります。あなたが適切なアルゴリズムを実装する場合

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 
    } 
} 

、時間の複雑さは、平均的なケースと最悪のケースでO(n^2)にO(nlogn)になります。