分配算法/可用性算法

Question

我想知道是否有任何算法可以帮助我解决以下问题：

将人员（n）分配到特定的活动（m），每个m只能与一个人相关联，且每次必须随机分配（如果只有一种选项可用，则允许相同的人(n)）。n具有可用时间和可用日期等属性。为了将n匹配到m，n和m的可用时间和日期必须匹配。可能会有多个n与m的时间匹配，但必须是最佳匹配，以便分配其余的m。下面的图表很可能会更好地解释它（抱歉）。n可以分配给多个m，但应该公平地进行，以防止一个n获得所有可用的m。

如您所见，Person A可以附加到Event A，但由于需要使它们全部匹配（尽力匹配），因此将其附加到Event B，以允许将Person C分配到Event A，将Person B分配到Event C。

我只是想知道这种类型的问题的名称以及我如何解决它，我正在使用Java编写程序。

- user2013520

---

乍一看，它似乎是背包问题的一个版本。 - Amir Afghani

@AmirAfghani 我不太确定——假设解决方案存在，不同的解决方案之间没有相对的“价值”。 - Kyle Strand

那么每个人只能参加一个活动，即使他们可以参加两个没有重叠时间的活动？ - Kyle Strand

只要事件不重叠，一个人可以有多个事件。 - user2013520

你能为事件定义“重叠”吗？ - Mshnik

Answer 1

这是最大流问题的一种变体。有许多算法专门用于解决最大流问题，包括Ford-Fulkerson算法或其改进版Edmonds-Karp算法。一旦您能够将问题转化为最大流问题，解决它就相当简单。但是什么是最大流问题？

该问题接受一个加权有向图，并询问“从源（一个节点）到汇（另一个节点）可以定向的最大流量是多少？”有一些限制条件，在将图形视为水流网络时具有逻辑意义。

1. 对于图中的每条边，流经该边的流量必须小于或等于该边的“容量”（权重）。它们还必须是非负数。
2. 除源点和汇点外，每个节点的流入量必须等于离开该节点的流出量。通过节点的流量没有限制。

考虑以下图形，其中s为源，t为汇。

最大流问题的解决方案将是总流量为25，其中包括以下各流量：

将您的问题转化为最大流问题非常简单。假设您的输入如下：

• N 个人，以及有关每个人 p_i 可用时间和日期的相关信息。
• M 个带有时间和地点的事件。

创建一个具有以下属性的图：

• 一个超级源点 s
• N 个人节点 p_1 ... p_n，对于所有的 i in 1 ... n，连接 s 和 p_i 的边容量为 无限大。
• 一个超级汇点 t
• M 个事件节点 e_1 ... e_m，对于所有的 i in 1 ... m，连接 e_i 和 t 的边容量为 1。
• 对于每个人和事件的组合 (p_i, e_j)，当且仅当 p 可以有效地参加事件 e 时（否则不连接 p_i 和 e_j），连接 p_i 和 e_j 的边容量为 无限大。

按照这些规格构建图的运行时间为 O(1) + O(N) + O(N) + O(M) + O(M) + O(1) + O(NM) = O(NM)。

对于你的示例，构建的图看起来像下面这样（没有标签的边具有无限容量）：

你正确地注意到这个例子中有一个最大流值为4，任何最大流都会返回相同的值。一旦你能执行这种转换，你就可以运行任何最大流算法并解决你的问题。

- Mshnik

---

我该如何更改代码以确保m(Events)只能有一个人与之相关联。目前，事件可以有多个人。 - user2013520

实际上，事件不能有多个人。请注意，容量为“1”的边缘离开事件节点，因此最多只能进入这些节点的“1”个流而不违反约束条件（2）。另外，根据您在OP上的评论，我已编辑了图形创建，允许用户参加他们想要参加的所有活动。 - Mshnik

加10分给你在回答中的专注度 - hcarrasko

Answer 2

创建一个名为AllocatePerson的类，该类具有称为lsInnerEvents的属性的Person和事件列表（您必须首先定义Person类和Events类，两者都具有时间和日期列表）。

在AllocatePerson的构造函数中，您将提供一个Person和一个事件列表，构造函数将循环遍历事件，并仅将与Person参数匹配的事件添加到内部列表中。

主代码将为每个人创建一个AllocatePerson（一次1个），实现以下逻辑：

如果新创建的对象“objAllocatePerson”具有大小为1的lsInnerEvents列表，则从要分配的事件列表中删除包含在lsInnerEvents中的元素，并触发一个名为MaintainEvents（已分配的事件）的过程。

MaintainEvents函数将循环遍历当前的AllocatePersons数组，并从它们的lsInnerEvents中删除“removedEvents”，如果此后lsInnerEvents的大小为1，则会递归调用MaintainEvents（）以获取新的已删除事件，并从主要的要分配的事件列表中删除新的lsInnerEvents。

执行结束时，您只需通过循环遍历AllocatePersons数组即可获得所有关联，其中lsInnerEvents大小为1。

- SeraphimFoA

Answer 3

一个可以考虑的方法如下：

1. 创建Java对象以表示人员和事件。
2. 将所有事件放入池中（Java集合）。
3. 让每个人员从池中选择一个事件。由于每个人只能在特定的日期选择事件，因此需要为事件创建一个子集，以便从人员中选择。

为事件添加必要的属性，以确保它只能被一个人员选择一次。

- Rami Del Toro