問題タブ [disjoint-sets]

与えられた締め切りと迅速な完了での利益でジョブをスケジュールするために、実行可能なタスクのすべてのセットからの利益を最大化する貪欲なアルゴリズムが提案されています。

ただし、推奨されるプログラムによる実装は、互いに素なセット フォレストです。

この実装を示す文献を見つけることができませんでした（コンピューターサイエンス/数学以外のバックグラウンドには十分簡単です）。

このようなプログラミング言語にとらわれない実装への参照は大歓迎です。

私がやりたいのは、( n ) 個のアイテムのグループを同じサイズのグループ (サイズmのグループ。簡単にするために、残り物がない、つまりnはmで割り切れると仮定します) に分割することです。これを複数回行うことで、アイテムのペアが同じグループに 2 回含まれないようにしたいと考えています。

これをもう少し具体的にするために、6 つの項目のうち 2 つのグループを構築するためにA..F、さまざまな方法でセットを 5 回分割することができます。

• (A, B)、(C, D)、(E, F)
• (A, C)、(B, E)、(D, F)
• (A, D)、(B, F)、(C, E)
• (A, E)、(B, D)、(C, F)
• (A, F)、(B, C)、(D, E)

同じアイテムのセットは、ペアを重複させずに 3 つのグループに 1 回だけ分割できます。

• (A, B, C)、(D, E, F)

_{（@DavidHammenが以下で指摘しているように、この例ではパーティションを作成するさまざまな方法があります。ただし、パーティションを一度作成すると、アイテムのすべてのペアを分離する別の2番目の分割はありません。それは問題ありません-私のアプリケーションはそうではありませんセットをグローバルに分割する可能性のあるすべての方法を生成する必要はなく、制約を満たす 1 つのソリューションで十分です)}

私の質問は次のとおりです。これを効率的に行う方法はありますか? これらのセットの生成を高速化するためのトリックはありますか?

これまでのところ、私はこれを正確なカバー問題として扱い、バックトラッキング アルゴリズム(DLX の変形) で解決してきました。これはペアの場合は非常にうまく機能しますが、グループが大きくなると、アルゴリズムが考慮しなければならない可能性の数が爆発的に増加し、処理が非常に扱いにくくなります。

私が探しているのは、物事をスピードアップするためのトリックです。特に、どんなアイデアも大歓迎です（ただし、これらに限定されません）：

• 解決する前に考慮する必要がある可能性の数を減らすための最適化とヒューリスティック(たとえば、上記の例から明らかなように、最初の分割は単純に任意に行うことができ、各パーティションの最初のセット [上の最初の列] ] を自動的に生成できます)。
• 膨大な数の候補者に対処できるバックトラッキングのバリエーションはありますか? (つまり、事前にすべての可能性を生成する必要はありません)
• 考慮すべき他のアルゴリズム、アプローチ、または数学的概念はありますか?

どんなアイデアや提案も大歓迎です。ご検討いただき誠にありがとうございます！

アップデート

わかりました、これはしばらく経ちましたが、私はこれにもっと多くの時間を費やしたので、あなたに戻ってきたいと思いました. @david-eisenstat は、正しい検索用語を教えてくれたことで、私を正しい道に導いてくれました (どうもありがとうございました!)。それ以来、Social Golfer Problem についてかなりの量の記事を読みました。

私が見つけた最高のリソースの 1 つは、ここで共有したいMarkus Triskaの論文です。彼は論文でいくつかのアプローチについて説明しています (その後、非常に優れたアルゴリズムを提示しています)。誰かが同様の問題に遭遇した場合、これは強くお勧めします!