表格/座位分配算法

Question

我目前正在开发一个预订系统，并且需要一种基于某些条件和预定义值为公司参与者分配座位的算法。

这些条件是：

• 从每个不同的公司，至少两个参与者必须放在同一张桌子上。(考虑到该公司至少有2名参与者)
• 公司有自己的竞争对手。公司不能和竞争对手坐在同一张桌子上。

预定义的值是：

• 桌子和座位是预先定义的。
• 公司、参与者和竞争对手的关系是预先定义的。

实体的定义：

表： ID (Int，PK)、描述(字符串)、数字(Int)、

TableSeat: ID (Int，PK)，编号(Int)，TableID ( FK)，CustomerID (无空Int，FK)

公司： ID (PK)名称(String) DefaultNumberOfParticipants (Int) CompetitorID (FK)

竞争对手： ID (PK) CompanyID (FK) CompanyID2 (FK)

因此，例如，如果我已经定义了以下预置：

表：

• 表1有6个座位
• 表2有4个座位
• 表3有6个座位
• 表4有3个座位

公司/参与者：

• Company1有3个参与者，没有竞争对手
• Company2有2名参与者，Company3为竞争对手
• Company3有4名参与者，Company2为竞争对手

我需要自动分配总共9名参与者，来自3家公司的4张桌子上总共有19个座位。根据条件，Company2和Company3的参与者不能坐在同一张桌子上。此外，当一个参与者坐在一张桌子旁时，他应该由一位同事陪同(如果可能的话)。

任何关于合适算法的想法或指示都将不胜感激。谢谢。

Answer 1

您可以在此算法上尝试以下变体：将播放机分发到表中

再一次，总的想法是依次处理每一张桌子上的每个座位，让一个随机的剩余的、有效的人坐在那里。如果没有这样的人可用，算法终止没有结果(使它成为一个所谓的拉斯维加斯算法)。

取决于有多少有效的解决方案，在找到一个解决方案之前，您可能需要运行几次算法，但这是可以的，因为一次运行是如此之快:我估计，对于您给出的例子，您应该在不到一秒钟内找到一个结果，至少比对所有可能的排列进行彻底的搜索要快得多。

不允许2名参赛者坐在同一张桌子上的条件可以很容易地得到执行:当选择下一个人坐在一张桌子上时，只需排除所有已经坐在该桌上的人的竞争者。

另一个条件是，一个人最好至少有一个同事坐在一起，这是很难做到的。它仍然可以作为一个硬约束来实现，但我怀疑可能会有大量的情况不会产生任何结果。

因此，我建议把这个条件变成一种“软约束”，最初完全忽略这个条件，但在评估结果后，对每一个没有和同事一起坐的人给予一个罚分。

这保证了即使在不是每个人都能和同事一起坐的情况下，你仍然会得到一个可以接受的座位。

然后，该算法成为：

//Place everyone at a table while avoiding seating competitors together
for each table T:
   UP = a randomly shuffled list of unseated people
   for each person X from UP
      While there still is at least one seat available at T AND
          X is not a competitor of anyone already seated at T
             seat X at T

   if T still has one or more seats available
      abort;  //With the decisions taken so far, noone can be seated at T. This run has no result.

//Complete seat configuration found. Award a penalty point for evey person not seated with a colleague.
penaltyPoints = 0
for each table T:
   for each person X seated at T
      If there is no other person at T that is from X's company
         Add a penalty point.

运行这个算法好几个？千人？)用最少的罚分来保持结果的次数。

Answer 2

我认为这个问题可以归结为图的顶点着色。竞争对手公司的参与者在图中是连接的。颜色的数目等于表的数目。还有一个附加的约束，即每个颜色/表都有最大数量的与之关联的节点。

至于同一公司至少有两个人需要坐在同一张桌子上的问题，每当你给一个新节点着色时，忍受同一公司的另一个节点的颜色相同，否则就尝试用相同的颜色给同一公司的另一个节点着色。