を要求する最適な子供の野球チームを作るが、私は今、私の武器庫を持っているすべての分枝限定と遺伝的アルゴリズムであるので、多くのグラフ理論を知りません。それほど強力ではありませんが、私はここで学びます。アルゴリズム：満たすアルゴリズムを記述しようとすると
は、ここに私の問題だ： チームあたりLの選手とのk個のチームに入れなければ我々は、n個の子供たちのセットを持っています。それぞれの子供は、チームで最大3人の友人に遊ぶように要請します。それぞれの子供は、彼らの要求の一つが満たされていることが保証されています。
私たちは、チームごとにLの選手のcontraint対象満たさ要求の数を、最大化し、それぞれの子が少なくとも一つの成就の要求を持っているようにチームのセットを最大化します。私が研究になるはずアルゴリズムのどのような種類
？私はこれがグラフ理論の応用であると考えています。各プレイヤーはノードであり、各要求はエッジです。しかし、私のグラフ知識の程度についてはそれがあります。
あなたができることは、説明したようにグラフを作成し、少なくともすべてのプレイヤーの要求の1つが確実に実行されるようにPrimのアルゴリズム（最小スパニングツリー）を適用し、次にエンドノードで開始し、
これは、複数のサブグラフ（互いに要求する2つのグループのプレイヤー、もう1つのグループにない2つのプレイヤー）が存在しないことを前提にしていますが、少なくともプリムを実行することで、どのプレイヤーがどの友達とペアになるのかを絞り込むことができます。
MSTアルゴリズムがスター構造ツリーを選択するとどうなりますか？ （すなわち、1つのノードが1つおきのノードに接続される）。各エッジは等しく重み付けされているので、これが可能です。 – ElKamina
@ElKaminaそれはありそうもないですが、私はあなたの意見を見ます。プレイヤーは他の人が選んだが、成就彼または彼女の選択肢のいずれかを持っていない可能性があるため、私は私のオリジナルの答えでは考慮していない他の事は、（このプレイヤーは、そのプレイヤーを選択）エッジは、方向性でなければならないことです。 – saluce
私はそうは考えていないだろう。これは、次のエッジ選択するために使用されるロジックの小片に依存するであろう（それは平等をどのように処理するかを？それはノード番号でソートした場合、このシナリオは非常に可能性があります）。とにかく、あなたが言及している心配も非常にありそうですか？どのようにそれに対処しますか？接続され、少なくとも1つのループを持ち、すべてのノードが出力エッジを持つサブグラフのセットを見つける必要があります。 – ElKamina
これは宿題に問題がありますか？あれば、宿題にしてください。 – saluce
それはありません！私の友人だけがリーグを運営しています。彼を助けるために私を教えてください。 – JoshDG