0

私は 20 人のグループ (ラベル1 - 20) を取り、誰と一緒にいたいかという明確な好みに基づいて、それぞれ 4 人ずつの 5 つのサブグループに分けようとしています。

20 人のグループの各人は、0、1、2、3、または 4 つの好みを表現できます。たとえば、person10 (一緒にいる人の好みがない)、または 14 (とのグループperson14) を選択するか、14、20、6、および 7 人のグループにいることを表すことができます。理想的には、好みを持つ各人は少なくとも 1 つの選択肢があるグループに属します。

アルゴリズムのアイデア？

4

2 に答える 2

2

あなたが抱えている問題は、実際には C# とは関係ありません。アルゴリズムは言語に依存しません。

この問題の古典的な実装はbacktrackingです。

より詳しい情報：

別のアプローチ（私はこれに行きます）：遺伝的アルゴリズム。

于 2009-08-09T13:41:24.473 に答える
0

これは SO に尋ねるには多すぎるかもしれませんが、問題は非常に興味深いと思うので、ここにいくつかの考えを示します。

Victor Hurdugaciが言うように、これは主に言語に依存しないアルゴリズムの問​​題です (ただし、以下の例が LINQ で実装されているのを見てみたいです!)

あなたの質問で説明されている問題は、完全な結果をもたらすことはできません。つまり、それは最適化問題です (したがって、制約統計アルゴリズムで解決することはできません)。結果の良さを示す何らかの関数 (フィットネス関数と呼ばれる) に基づいて、考えられるすべての結果のセットから最良の結果を見つけるアルゴリズムを見つける必要があります。

素朴なブルート フォース ソリューション (疑似コード)

人々のセットから始めます (ここでは単純化するために 4 人):

people = { a, b, c, d }

choose演算子を使用して、固定サイズ (ここでは 2) のすべての可能なサブグループを見つけることができます。

groups = people.choose(2)  // = { {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} }

choose演算子を再度使用して、サブグループのすべての可能な組み合わせを見つけることができます。

combi = groups.choose(4/2) // = { {ab,ac} {ab,ad} {ab,bc} {ab,bd}
                           //     {ab,cd} {ac,ad} {ac,bc} {ac,bd}
                           //     {ac,cd} {ad,bc} {ad,bd} {ad,cd}
                           //     {bc,bd} {bc,cd} {bd,cd} }

明らかに、人々が同時に 2 つのグループに属することはできないため、無効な組み合わせをすべて削除します。

combi2 = combi.select(g => g.bigUnion().size == 4)
                           // = { {ab,cd}, {ac,bd}, {ad,bc} }

ここで、フィットネス関数に基づいて「最良の」アイテム、つまり好みを考慮して最高のスコアが得られる組み合わせを見つける必要があります。

result = combi2.maximumBy(g => fitness(g))

たとえば、 とにa優先度があり、 に優先度がない場合、とよりも に対して高いスコアを返す必要があります。bbcdcalculateScore{ab,cd}{ac,bd}{ad,bc}

改善されたソリューション

この種の最適化問題を扱うアルゴリズムはいくつかあります。ヒル クライミングアルゴリズムがここに適していると思います。

于 2009-08-09T14:11:53.620 に答える