0

では、この問題を解決するためのソフトウェアを書きたいと思います。

ビジネス オーナーが一定時間、テーブルで他のビジネス オーナーと話すネットワーキング イベントがあります。イベントには n 人が参加し、1 つのテーブルに座ることができる人数は s で、テーブルは t あります。

割り当てられた時間が経過した後、すべての人が何らかの方法でシャッフルして、新しい人と話すことができるようにします. アイデアは、イベントに参加するすべての人に、冗長な接続をできるだけ少なくして他の人と話す機会を与えることです (完全なグラフ)。

グラフが 100% 完全である必要はありませんが、可能な限り近い方がよいでしょう。

変数を要約するには (現実的な値で):

    n - the number of people attending the event (20-40)
    s - the number of people who can sit at one table(5-8)
    t - the number of tables (4-10)
    c - the number of shuffles (what ever is required for the setup)

したがって、グラフ理論の経験はまったくありませんが、これは問題を解決するための大まかなアイデアです。

  1. 可能なすべての接続のリストを形成します。それらの (n* (n-1))/2 があります。
  2. テーブルが適切な人数になるまで、一度に 1 つの接続されていない接続を追加してテーブルを作成します。
  3. 冗長接続を作成しない接続を追加してみてください
  4. 人が複数のテーブルに座る結果になる場合は、テーブルに接続を追加しないでください。
  5. すべての接続が使用されるまで、これを繰り返します。

これがどのように機能するか/実装するかについて考えるのに苦労しています。誰かが私にアドバイスをくれたり、正しい方向に向けてくれることを願っていました。

ありがとう

4

1 に答える 1

0

これは、分割グラフ問題またはクリーク問題のバリエーションのように聞こえます。

これは比較的複雑な問題であり、正確な解決策を必要としないという事実は、「許容できるほど良い」解決策を得るために実際に何をする必要があるかを判断することを困難にします。現在の状況に合ったものが見つかることを期待して、最初にこれらの2ページを読むことをお勧めします。

完全グラフから逆方向に作業することが最善の戦略である可能性があることに同意します。完全なグラフから始めて、それをコンポーネントに分割して、配置を取得しようとします。提案されたアルゴリズムはうまくいくかもしれません。試してみて、うまくいかない場合は別の質問をするのがおそらく最善です:)

于 2012-11-03T22:08:37.270 に答える