11

私の結婚式には x 人のゲストがいて、z 席のテー​​ブルは y です。ゲストAはゲストBと同じテーブルに座ることができ、ゲストCはゲストDと同じテーブルに座ることはできません....

すべてのゲスト間のすべての接続のデータセットが与えられた場合、この種の問題を解決できる既知のアルゴリズムはありますか?

この種の問題には、「問題x」または何かとして知られる抽象的な親があると確信しています。または、アルゴリズムyとzを組み合わせることで解決できる問題aと問題bの構成である可能性があります

正しい方向のポイントは高く評価されます。

4

4 に答える 4

7

正確な解が必要な場合は、0-1 の整数プログラムとして定式化し、GLPK を使用して解いてください。

個人 i がテーブル j に割り当てられている場合は x_ij を 1 とし、それ以外の場合は 0 とします。次の制約セットを検討してください。

(i) sum_{j=1...y} x_ij = 1 for i=1...x

(ii) sum_{i=1...x} x_ij <= z for j=1...y

(iii) x_ij + x_kj <=1 for j=1...y

(iv) x_ij はバイナリ

制約 (i) 全員が割り当てられていることを確認します。制約 (ii) は、テーブルのオーバーロードを防ぎます。制約 (iii) は、一緒に座ることができない人物のペア (i、k) ごとに定義されます。

それを GLPK、CPLEX、または GUROBI に接続すれば、問題が大きすぎない限りビジネスになります。他の人が述べたように、NP 困難性は、物事が醜くなる可能性があることを意味します。

于 2013-10-02T19:31:27.220 に答える
5

この問題は一般的に NP 困難であるため、テーブルまたはゲストの数が多い場合に効率的な一般的な解決策を見つけることは期待できません。この問題は、好みに基づいて人々を異なる家に分割することについて尋ねるこの以前の問題のバリエーションであり、各テーブルにすべてを保持するのに十分な容量を与えるだけで、その問題 (NP 困難) をこの問題に減らすことができます。ゲスト。

テーブルごとの人数が少なく、ゲストの数も少ない場合は、考えられるすべての割り当てを試すことで、解決策を力ずくで試すことができます。もう 1 つのオプションは、いくつかの解をランダムに推測してから、それらを段階的に変更して、機能する解を見つけようとすることです (たとえば、山登りアルゴリズムを使用します)。

お役に立てれば！

于 2013-10-02T17:55:36.080 に答える
1

これは NP 困難な問題であるため、一般的な解は見つかりません。実際、1 つのテーブルに一緒に座れる z 人のゲストを見つけることさえ NP 困難です。

ただし、ゲストの競合があまりない場合は、おそらくヒューリスティックが機能します。例えば：

Pick an unseated guest G with a maximal number of incident edges (conflicts)
  If G has a conflict with someone seated at each table, then fail
  Else assign G at random to an available table
Repeat until all guests are seated

わずかに優れたヒューリスティックには、各ゲストの可能なすべてのテーブルを追跡することが含まれます。最初は、各ゲストはどのテーブルにも座ることができます。

Pick an unseated guest G such that the size of G.availableTables is minimal
  If G.availableTables is empty, then fail
  Assign G at random to a table T from G.availableTables
  For each guest G2 who is in conflict with G
    remove T from the set G2.availableTables
Repeat until all guests are seated.

このヒューリスティックを変更して、テーブル T ごとに、残りの席を埋めることができる未着席のゲストの数を追跡して、さらに強力にすることもできます。そして、ゲストをテーブルに割り当てるとき、無作為に選ぶのではなく、残席が多く、座ることができる人が少ないテーブルを優先的に選択します。

実際には、このようなヒューリスティックが無作為に数百回試行してもうまくいかない場合、おそらく解決が難しい問題になるでしょう。

于 2013-10-02T19:19:51.287 に答える