6

私がやりたいのは、( 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の論文です。彼は論文でいくつかのアプローチについて説明しています (その後、非常に優れたアルゴリズムを提示しています)。誰かが同様の問題に遭遇した場合、これは強くお勧めします!

4

2 に答える 2

0

n=m*kとすると、パーティションにはアイテムをm含むグループがありkます。

分割後x、各アイテムはx*(k-1)他のアイテムとグループ化されます。パーティションを作成した後t-1、次のパーティションで次Aを選択できます。

second element : n -   (t-1)*(k-1)   - 1  items
third element  : n - 2*(t-1)*(k-1)   - 2  items
fourth element : n - 3*(t-1)*(k-1)   - 3  items
...
k'th element   : n -   (t-1)*(k-1)^2 - (k-1)  items

t'thパーティションを作成するには、次のものが必要です。

n - (t-1)*(k-1)^2 - (k-1) > 0
=>
t < (n - k + 1) / ((k-1)^2) + 1

可能な分割の数は、グループの長さの 2 乗で減少します。つまり、可能なパーティションが多すぎないということです:-)

私は貪欲なアプローチで行きます。利用可能なアイテムのセットごとに保存し、最初の利用可能なアイテムをグループに追加して新しいパーティションを作成します。

于 2015-09-27T10:12:25.530 に答える