メンターリングイベントのためのアルゴリズム開発

Question

私はメンタリングの各「ラウンド」において1-4人のメンターの異なるグループとメンティーをペアにするアルゴリズムを作成しようとしています。

アルゴリズムは、3つの入力受け入れる：

• をメンティーの数 - 1と

• 35の間の整数

  メンターの数 - 常に以上メンティーの数に等しく、

を実行するために指導のラウンド数35

よりますが大きいことはありません

これら三つの入力を考えると、このアルゴリズムは、次の制限で、1-4メンターとメンティーそれぞれにマッチします：

• それは与えられた入力でそうすることが可能である場合は、メンティーがペアてはなりませんそれは与えられた入力でそうすることが可能である場合は、同じメンターと複数回

• は、メンターは別のメンター回以上

注意としてメンターの同じグループになることはありませんする必要があります。ザアルゴリズムはメンターをランダムにメンティーに割り当てる必要はありません。コードは、同じ入力セットで実行されるたびに同じ出力を与えることができます。ここで

は2ラウンド、4人のメンティー、および11人のメンターで成功アルゴリズムの出力例を示します。

| Round | Mentee | 1 | 2 | | 1 | 1, 2, 3| 4, 7, 10| | 2 | 4, 5, 6| 1, 8, 11| | 3 | 7, 8, 9| 2, 5 | | 4 |10, 11 | 3, 6, 9 |

ご質問があれば私に知らせて、または私は何場合してください実際には不可能であることを求める。あなたの時間と援助に感謝し、素晴らしい一日を過ごしてください。

敬具、 Tyrovar

Answer 1

興味深い問題！

私が知っている効率的な建設的な解決策を持たない長期的なコンビナトリアルな問題に関連しているので、残念なことに、それは速い解決策を持つことはまずありません。

次の2つの部分で問題と考えることができます：メンティーと（1）各ラウンドのためにメンターのグループを決定した後、（2）ペアリングこれらのグループ。

nメンターの数とメンテの数を呼び出します。そして、mがnを均等に分割すると仮定します。

次に、各ラウンドのメンターのグループを把握するための最初の部分（1）は同等です（十分な数のラウンドを使用しています） S(2, n/m, n)Steiner Triple Systemが見つかりました。これらのコンビナトリアルオブジェクトに関する研究は数多く行われていますが、一部のアルゴリズムは公開されていますが、私の知る限り、それらはどれも高速ではなく多項式時間でもありません。

しかし、合理的なパラメータの大きさのために、あなたは貪欲アルゴリズムアプローチで指導者のグループを生成することを望むことができます。各メンターについて、他のメンターそのメンターがになっていたの（setデータ構造内）を追跡しグループは既にあります。各ラウンドについて、グループにまだ参加していないメンターのグループを作成してから、それらのグループメンバーを各リストに追加します。しかし、これが失敗した場合、グループを見つけるためには強引なアプローチに頼らなければならないかもしれません。

メンターのグループを取得したら、各ラウンドのメンティーとペアリングしてbipartite perfect matching problemのインスタンスになります。これには、Hopcroft-Karp algorithmを含むいくつかの合理的な効率的なソリューションがあります。繰り返しますが、各メンティーが見たメンターを追跡し、各ラウンドでこれを更新したいと考えています。

ので、一般的に、私は示唆しているアプローチは、次のとおりです。

1. 空当初は、すべてのメンターのために、すべてのメンティーのためのメンターのsetを作成します。
2. Greedilym/nのグループは、以前は同じグループに属していなかったそれぞれnのグループです。あなたが "つまらない"場合は、適切なものが見つかるまで brute-forceのすべての可能なグループに絞って検索してください。
3. 各メンティーに1つの頂点、現在のラウンドにメンターのグループ、メンターの1つの頂点、グループ内のメンターの誰もまだそのメンティーを見ていない場合は、それらの間にエッジがある2つのグラフを作成します。
4. このグラフで最大のマッチングを見つけます - これは、現在のラウンドのメンティーとメンターのペアです。
5. 残りのラウンドで手順2〜4を繰り返します。

あなたが尋ねている内容と密接に関連しているKirkman's Schoolgirl's Problemを見てみるとよいでしょう。一般的に解決が難しい理由を簡単に説明してください。