java - 分配算法/可用性算法

Question

我想知道是否有人知道我可以用来帮助我解决以下问题的算法:

将人 (n) 分配给某些事件 (m)，m 只能有一个人与之关联，并且每次都必须随机分配(如果只有一个选项可用，则允许同一个人(n))。 n 具有可用时间和可用日期等属性。要使 n 与 m 匹配，可用时间和可用日期必须与 n 和 m 匹配。可以有多个 n 与 m 的时间相匹配，但它必须是最合适的，以便可以分配 m 的其余部分。下图很可能会更好地解释它(抱歉)。 n 可以分配给多个 m，但应该公平地分配，这样一个 n 就不会拥有所有可用的 m

如您所见，A 可以附加到事件 A，但由于需要让它们全部匹配(最好的匹配尝试)，它附加到事件 B 以允许将 C 分配给事件 A 和人员B 到事件 C。

我只是想知道是否有人知道这类问题的名称以及我该如何解决它，我正在用 Java 编写程序

Answer 1

这是 Max Flow Problem 的变体.有许多算法可以解决最大流量问题，包括 The Ford-Fulkerson Algorithm或其改进，Edmonds-Karp Algorithm .一旦你能够将你的问题变成最大流问题，解决它就相当简单了。但是最大流问题是什么？

该问题采用加权有向图并提出问题“从源(一个节点)到汇(另一个节点)的最大流量是多少？”。将图形视为水流网络时，有一些限制在逻辑上是有意义的。

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

考虑下图，s 作为源，t 作为汇。

最大流量问题的解决方案是总流量为 25，流量如下:

将您的问题转换为最大流问题很简单。假设您的输入是:

• N 个人，以及有关个人 p_i 何时有空的时间和日期相关信息。
• M 个具有时间和地点的事件。

创建具有以下属性的图形:

• 一个 super 源s
• N 个人节点 p_1 ... p_n，边容量 infinity 连接 s 到 p_i 表示 1 ... n 中的所有 i。
• super 接收器 t
• M 事件节点 e_1 ... e_m，边缘容量 1 连接 e_i 到 t 表示 1 ... m 中的所有 i
• 对于每个人和事件的组合 (p_i, e_j)，一条容量为 infinity 的边将 p_i 连接到 e_j 当且仅当 p 可以有效地参加事件 e(否则没有边连接 p_i 和 e_j)。

根据这些规范构建图表的时间为 O(1) + O(N) + O(N) + O(M) + O(M) + O(1) + O(NM) = O( NM) 运行时。

对于您的示例，构建的图如下所示(未标记的边具有无限容量):

您正确地注意到此示例中有一个值为 4 的最大流量，并且任何最大流量都将返回相同的值。一旦您可以执行此转换，您就可以运行任何最大流算法并解决您的问题。