表/座位分配算法

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

的条件是：

从每个不同的公司，至少两个参与者必须放置在相同的表。（鉴于该公司至少有2名参与者）
公司有竞争对手的定义。公司不能与竞争对手坐在同一张桌子上。

预定义的值是：

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

实体的定义：

表： ID（中间体，PK），描述（字符串），号（INT），

TableSeat： ID（中间体，PK）， Number（Int）， TableID（FK）， CustomerID（Nullable Int，FK）

公司： ID（PK）名称（字符串） DefaultNumberOfParticipants（INT） CompetitorID（FK）

Competior： ID（PK） CompanyID（FK） CompanyID2（FK）

所以，如果我，例如，有以下预设定义：

表：

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

公司/参加者：

Company1有3个参与者，没有竞争对手
Company2 h作为2名参与者和公司3作为竞争对手
公司3有4名参与者和Company2的竞争对手的

我需要自动分配共有9人参加，从3家公司上4代表总数的19席。根据条件，公司2和公司3的参与者不能坐在同一张桌子上。此外，当一个参与者坐在桌旁时，他应该由同伴参与者陪同（如果可能的话）。

任何想法或指向一个合适的算法将不胜感激。谢谢。

来源

2014-10-30 MartinChristensen

如果你想快速编程，你可以尝试'贪婪随机'metaheuristics（GRASP）http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure – Seb 2014-10-30 13:01:24

你可以试试下面的变化对这个算法：Distributing players to tables

同样的总体思路是对的过程依次在每个表中的每个座位，在座位是随机的剩余和有效的人。如果没有这样的人可用，则该算法终止而没有结果（使其成为所谓的Las Vegas算法）。

取决于有多少有效的解决方案，您可能必须在找到解决方案之前运行该算法几百次，但这是正确的，因为单次运行非常快：我估计，对于你给出的例子，你应该在不到一秒的时间内找到结果，至少比通过所有可能的排列进行彻底搜索要快得多。

没有竞争对手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.

运行该算法几个（？十万）次，并保持与结果的点球点数量最少。

来源

2014-10-31 19:39:31 Astrotrain

我觉得这个问题可以简化为图的顶点着色。竞争对手公司的参与者连接在图中。颜色的数量等于表的数量。还有一个附加约束条件是每个颜色/表格都有最大数量的节点与其相关联。

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

来源

2014-10-30 13:33:40 navari

表/座位分配算法

回答

相关问题