12

私はコンサルティング組織で働いており、ほとんどの場合、顧客の場所にいます。そのため、同僚に会うことはめったにありません。お互いをよりよく知るために、ディナーパーティーを手配します。小さなテーブルがたくさんあるので、人々はチャットをすることができます。パーティー中にできるだけ多くの人と話すためには、全員が一定の間隔で、たとえば1時間ごとにテーブルを切り替える必要があります。

テーブル切り替えスケジュールを作成するプログラムを作成するにはどうすればよいですか？いくつかの数字を与えるためだけに。この場合、約40人が参加し、各テーブルには最大8人が参加できます。ただし、アルゴリズムはもちろん一般的なものである必要があります

4

9 に答える 9

12


ここに、一人称の観点からの最初の作業のアイデアがあります..彼をX
Xと呼びましょう。部屋の他のすべての人に会う必要があるため、残りの人をn個のグループ（n = #_of_people / capacity_per_table）に分割する必要があります。反復ごとにこれらのグループの1つと一緒に座らせる
Xが処理されたので、次の人
YWLOGYを最初の反復自体でXが座らなければならなかった人と見なします。したがってYのテーブルグループはすでにわかっています。その時間枠では、残りの人をグループに分けて、各グループが連続する反復ごとにYと一緒に座るようにする必要があります。また、反復ごとに、XのグループとYのグループに共通の人がいない
と思います。このようなことを続ければ、最適な解決策が得られます（存在する場合）

または、食事をしたすべての人の名前を書き留めることができるカードを各人に渡すことで、問題をクラウドソーシングすることもできます。イベントの最後に、名前が最も多い人に何らかの賞品を贈ります。彼らのカード

于 2009-06-09T07:54:50.580 に答える
6

現実世界を真似てみませんか？

class Person { 
    void doPeriodically() {
         do {
             newTable = random (numberOfTables);
         } while (tableBusy(newTable))
         switchTable (newTable) 
    }
}

ああ、交配相手を見つけるための同様のアルゴリズムがあり、プログラミングの質問に答えるために自由時間をすべて費やさない99％の人々に効果的であると噂されていることに注意してください...

于 2009-06-09T20:25:44.267 に答える
6

これは、遺伝的アルゴリズムのアプリケーションのように聞こえます。

  1. 40 名のゲストからランダムな順列を選択します - これは 1 つの座席配置です
  2. ランダムな順列を N 回繰り返します (n は、夜に席を切り替える回数です)。
  3. 順列を組み合わせる - これが 1 つの生物の染色体です
  4. 一世代で繁殖させたい生物の数だけ繰り返す
  5. フィットネス スコアは、各人が 1 晩に会うことができた人の数です (または、会わなかった人の数の逆数)。
  6. 通常の方法を使用して新しい生物を繁殖、突然変異、導入し、満足のいく答えが得られるまで繰り返します

基本的な方法を大きく変更することなく、男性と女性の比率など、フィットネスに好きな他の要素を追加できます。

于 2009-06-09T08:26:46.723 に答える
4

パーフェクトテーブルプラン

于 2009-06-09T18:19:39.257 に答える
3

コンビナトリアルデザイン理論を見たいと思うかもしれません。

于 2009-06-09T09:13:11.233 に答える
2

直感的には、完璧なシャッフルよりもうまくできるとは思いませんが、それを証明するには、コーヒーを飲む前の私の認識を超えています.

于 2009-06-09T09:48:36.153 に答える
2

これはとても面白かったです！:D

私は別の方法を試しましたが、adi92 (カード + 賞品) によって提案されたロジックは、私が試した他のどの方法よりもうまく機能するものです。

それはこのように動作します：

  1. 男が到着し、すべてのテーブルを調べます
  2. 空いている席のあるテーブルごとに、まだ会わなければならない人数を数え、知らない人が多いテーブルを選ぶ
  3. 2 つのテーブルに見知らぬ人が同数いる場合、男性は空席の多い方を選択するため、より多くの新しい人に出会える可能性が高くなります。

各ターンで、座席を取る人々の順序はランダムです (これにより、無限ループの可能性が回避されます)。これは、Python で動作するアルゴリズムの「デモ」です。

import random

class Person(object):

    def __init__(self, name):
        self.name = name
        self.known_people = dict()

    def meets(self, a_guy, propagation = True):
        "self meets a_guy, and a_guy meets self"
        if a_guy not in self.known_people:
            self.known_people[a_guy] = 1
        else:
            self.known_people[a_guy] += 1

        if propagation: a_guy.meets(self, False)

    def points(self, table):
        "Calculates how many new guys self will meet at table"
        return len([p for p in table if p not in self.known_people])

    def chooses(self, tables, n_seats):
        "Calculate what is the best table to sit at, and return it"
        points = 0
        free_seats = 0
        ret = random.choice([t for t in tables if len(t)<n_seats])

        for table in tables:
            tmp_p = self.points(table)
            tmp_s = n_seats - len(table)
            if tmp_s == 0: continue
            if tmp_p > points or (tmp_p == points and tmp_s > free_seats):
                ret = table
                points = tmp_p
                free_seats = tmp_s

        return ret

    def __str__(self):
        return self.name
    def __repr__(self):
        return self.name


def Switcher(n_seats, people):
    """calculate how many tables and what switches you need
        assuming each table has n_seats seats"""

    n_people = len(people)
    n_tables = n_people/n_seats

    switches = []
    while not all(len(g.known_people) == n_people-1 for g in people):
        tables = [[] for t in xrange(n_tables)]

        random.shuffle(people) # need to change "starter"

        for the_guy in people:
            table = the_guy.chooses(tables, n_seats)
            tables.remove(table)
            for guy in table:
                the_guy.meets(guy)
            table += [the_guy]
            tables += [table]

        switches += [tables]

    return switches



lst_people = [Person('Hallis'),
      Person('adi92'),
      Person('ilya n.'),
      Person('m_oLogin'),
      Person('Andrea'),
      Person('1800 INFORMATION'),
      Person('starblue'),
      Person('regularfry')]    



s = Switcher(4, lst_people)

print "You need %d tables and %d turns" % (len(s[0]), len(s))
turn = 1
for tables in s:
    print 'Turn #%d' % turn
    turn += 1
    tbl = 1
    for table in tables:
        print '  Table #%d - '%tbl, table
        tbl += 1
    print '\n'

これにより、次のような出力が得られます。

You need 2 tables and 3 turns
Turn #1
  Table #1 -  [1800 INFORMATION, Hallis, m_oLogin, Andrea]
  Table #2 -  [adi92, starblue, ilya n., regularfry]


Turn #2
  Table #1 -  [regularfry, starblue, Hallis, m_oLogin]
  Table #2 -  [adi92, 1800 INFORMATION, Andrea, ilya n.]


Turn #3
  Table #1 -  [m_oLogin, Hallis, adi92, ilya n.]
  Table #2 -  [Andrea, regularfry, starblue, 1800 INFORMATION]

ランダムであるため、特に人数が多い場合は、常に最小数の切り替えが行われるとは限りません。次に、それを数回実行して、より少ないターンで結果を取得する必要があります (したがって、パーティーのすべての人にストレスを与えません:P)。コーディングは簡単です:P

PS: はい、賞金を節約できます:P

于 2009-06-11T23:29:48.607 に答える
1

安定したマッチング問題を見ることもできます。この問題を解決するには、max-flow アルゴリズムを使用します。http://en.wikipedia.org/wiki/Stable_marriage_problem

于 2009-06-09T18:10:32.360 に答える
1

私は遺伝的アルゴリズムを気にしません。代わりに、次のようにします。これは、完璧なシャッフルの繰り返しを少し改良したものです。

一方（会ったことのない人が2人います）：

  1. A と B が同じテーブルに座っていない場合、各ノードがゲストであり、エッジ (A、B) が存在するグラフを考えてみましょう。このグラフのすべての連結要素を見つけます。サイズが tablesize 未満の連結成分がある場合は、これらの連結成分をテーブルにスケジュールします。これも実際にはビン パッキングとして知られる難しい問題の例ですが、最初の近似の減少はおそらく問題ないことに注意してください。これは、接続されたコンポーネントを最大から最小の順に並べ替えてから、それぞれを配置することで達成できます。それらが収まる最初のテーブルを回します。
  2. 残りの要素のランダム順列を実行します。(つまり、残りの人をランダムに着席させます。最初は全員になります。)
  3. ラウンド数を示す増分カウンター。

ラウンド数が収束するようになるまで、上記をしばらく繰り返します。

于 2009-06-10T01:22:53.573 に答える