c# - table /座位分配算法

Question

我目前正在开发一个预订系统，需要一种算法来根据某些条件和预定义的值将公司参与者分配到座位。

条件是:

• 来自每个不同公司的至少两名参与者必须坐在同一张 table 上。 (鉴于公司至少有2名参与者)
• 公司定义了竞争对手。公司不能与竞争对手坐在同一张 table 上。

预定义的值是:

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

实体的定义:

表格:ID(Int，PK)，说明(字符串)，数字(整数)，

table 座:ID(Int，PK)，数字(整数)，表 ID (FK),CustomerID(可空整数，FK)

公司:身份证(公钥)名称(字符串)DefaultNumberOfParticipants(整数)CompetitorID (FK)

竞争对手:身份证(公钥)公司 ID (FK)公司 ID2 (FK)

因此，例如，如果我定义了以下预设:

表格:

• 第 1 table 有 6 个座位
• 2号 table 有4个座位
• 第 3 table 有 6 个座位
• 第 4 table 有 3 个座位

公司/参与者:

• 公司 1 有 3 个参与者，没有竞争对手
• Company2 有 2 名参与者，Company3 是竞争对手
• Company3 有 4 个参与者，Company2 是竞争对手

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

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

Answer 1

您可以在此算法上尝试以下变体:Distributing players to tables

同样，总体思路是依次处理每张 table 上的每个座位，让一个随机剩余的有效人坐在上面。如果没有这样的人可用，算法将终止而没有结果(使其成为所谓的 Las Vegas 算法)。

根据有效解决方案的数量，您可能需要运行该算法 100 次才能找到解决方案，但这没关系，因为单次运行非常快:我估计，例如你给了，你应该在不到一秒钟的时间内找到结果，至少比通过所有可能的排列进行详尽搜索要快得多。

不允许 2 名参赛者同 table 的条件很容易执行:选择时下一个就座的人，只排除该 table 所有已经就座的人的竞争对手。

另一个条件，即一个人最好与至少一位同事坐在一起更难做到。它仍然可以作为硬约束来实现，但我怀疑可能会有大量情况不会产生任何结果。
因此，我想建议将此条件设置为“软约束”，方法是最初完全忽略此条件，但随后通过为每个未与同事坐在一起的人扣分来评估每个结果。

即使在并非每个人都可以与同事坐在一起的情况下，这也保证了您仍然可以获得可接受的座位。

然后算法变成:

//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.

运行这个算法数次(十万？千？)次并保持惩罚次数最少的结果点数。