ゲーム用にある種のマッチメイキングアルゴリズムを作成しようとしているとします。このゲームはリーグや DOTA に似ており、5 人のプレイヤーが 5 人のプレイヤーと対戦します。さらに、プレイヤー プールが巨大 (一度に数百万人のプレイヤーがゲームを検索) であり、マッチ メーカーの仕事は、5 対 5 ゲームの多くのインスタンスにできるだけ多くのプレイヤーを配置することであるとします。現時点では、MMR、ELO、またはプレイヤー/パーティーの評価が影響することについてはまったく心配していません。プレイヤーを 5v5s に配置したいだけです。
私の現在のブルート フォース アルゴリズムは、スケーリングにおいてまったくひどいものです。最初に、数百万人のプレーヤーの中から 5 人のプレーヤー パーティーのすべての可能な組み合わせを見つけようとします。次に、パーティーのペアを見つけようとしますが、プレーヤーが既に使用されている場合は、可能なパーティー マッチからプレーヤーを削除します。
10 人のプレイヤーがいて、可能なすべての 5v5 を見つけたいとします。まずそれらをビットに変換し、ビット シフトを行ってすべての可能な組み合わせを見つけます。
Players: ABCDEFGHIJ
1111100000 => ABCDE
1111010000 => ABCDF
1111001000 => ABCDG
1111000100 => ABCDH
1111000010 => ABCDI
1111000001 => ABCDJ
1110110000 => ABCEF
等々...
次に、考えられるすべてのパーティーから、2 つの for ループを使用して、パーティーのペアを見つけようとします。
ABCDE vs FGHIJ
ABCDF vs EGHIJ
ABCDG VS EFHIJ
等々...
このアルゴリズムの実行時間は O((nCr)^2) です。考えられるすべてのパーティーの組み合わせを見つけようとするため、50 人のプレイヤーをマッチメイキングするだけでも 4.4891439e+12 の操作が必要になり、非常識です。
考えられるすべての関係者を通過せず、この問題を力ずくで処理する、より優れたアルゴリズムは何ですか?