桌子/座位分配算法

本文关键字：分配 算法 桌子 | 更新日期: 2023-09-27 18:28:21

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

条件是：

  • 每个不同的公司必须至少有两名参与者坐在同一张桌子上。（假设该公司至少有2名参与者）
  • 公司已经确定了竞争对手。公司不能与竞争对手坐在同一张桌子上

预定义值为：

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

实体定义：

表格：ID（Int，PK），描述（字符串），数字（Int），

桌座：ID（Int，PK），数字（Int），TableID（FK），CustomerID（Nullable Int，FK）

公司：ID（PK）名称（字符串）默认参与者数量（Int）竞争对手ID（FK）

竞争对手：ID（PK）公司ID（FK）公司ID2（FK）

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

表格：

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

公司/参与者：

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

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

任何关于合适算法的想法或指针都将受到极大的赞赏。谢谢

桌子/座位分配算法

您可以尝试此算法的以下变体：将玩家分配到表

同样，总体思路是依次处理每张桌子上的每个座位，随机安排一个剩余的有效人员。如果没有这样的人，算法就会终止，没有结果（这就是所谓的拉斯维加斯算法）。

根据有多少有效的解决方案，在找到解决方案之前，你可能需要运行算法100次，但这没关系，因为一次运行很快：我估计，就你给出的例子而言，你应该在不到一秒钟的时间内找到结果，至少比彻底搜索所有可能的排列要快得多。

不允许两名竞争对手在同一张桌子上的条件可以很容易地强制执行：当选择下一个坐在桌子旁的人，只需排除已经坐在那张桌子上的所有人的竞争对手。

另一个条件是，一个人最好与至少一位同事坐在一起，这更难做到正确。它仍然可以作为一个硬约束来实现，但我怀疑可能有相当多的情况不会产生任何结果
因此，我建议将这一条件设为"软约束"，最初完全忽略这一条件，但之后对每一个结果进行评估，对每个没有与同事坐在一起的人给予罚分。

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

然后算法变为：

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

运行此算法几次（十万？），并以最少的惩罚次数保持结果点。

我认为这个问题可以归结为图的顶点着色。竞争对手公司的参与者在图中相连。颜色的数量等于表格的数量。还有一个额外的限制，即每个颜色/表都有与其关联的最大节点数

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

相关文章：