algorithm - 自己選択チーム

Question

1000 名の応募者の中から 100 名のチームが編成されます。各応募者は、チームメイトにしたい他の 99 人の応募者を選ぶことができます。

可能な各チームは、メンバーのチームメイトの好みをどれだけ満たしているかを測定するスコアを取得します。リサがチームに属しており、リサのウィッシュリストにある 11 人もチームに属している場合、そのチームはリサに対して 11 ポイントを獲得します。メンバー全員のポイントが合算されます。チームが獲得できる理論上の最大値は 99*100 です。最小値は 0 です。

次に、スコアが最も高いチームを見つけたいと思います。考えられる各組み合わせ (≈ 10^140) のスコアを計算して、この問題を力ずくで解決しようとすることは選択肢ではありません。

最良の答えへの近道をする巧妙なアルゴリズムはありますか? それとも、良い答えを見つけるアルゴリズムに落ち着かなければなりませんか?

Answer 1

これを効率的に解決できれば、http://en.wikipedia.org/wiki/Clique_problemを効率的に解決できると思います.2つのノード間にリンクがあり、各ノードを他のノードが望むノードのリストに入れますと連携。この記事を見ると、問題に特別な構造がない限り、保証された適切な近似を見つけるのは難しいと思います。

Answer 2

山登りアルゴリズムを試してみてください。"人気のある" (他のメンバーによって最も頻繁に選ばれる) メンバーから始めて、チーム スコアを最も高くする新しいメンバーを段階的に追加します。残念ながら、これは最良の解決策を見つけることを保証するものではありませんが、おそらく良い解決策を見つけるでしょう。ソリューションを改善するには、シミュレートされたアニーリングを試すことができます。