最小化 session 日程冲突的算法

Question

是否有任何已知的算法帽子可以解决以下问题: 我们有一个 session ，有多个同时会谈。用户应标记感兴趣的会谈，然后我们要创建一个会谈时间表，以便我的大多数人都可以参加他们的会谈并最大限度地减少日程冲突。

这是否类似于具有已知解决算法的任何已知问题？

Answer 1

这听起来像是一个 NP 完全问题，因为搜索空间随着房间和讲座的数量呈指数级增长。

我认为您可以想出一些贪心算法，它会产生可行但可能不是最优的解决方案。

我想了想，想出了下面的算法。欢迎提出建议、改进和其他算法:)

假设有 m 个房间，每个房间有 l 个插槽，插槽对齐并且有 n 个参与者。然后最多会有 m*l 讲座。我将创建一个包含 # of lectures 顶点的完整图，其中的边将具有根据参与者偏好计算的权重。我将要求参与者提供有序的讲座列表。我将为每个位置分配一些值 - 例如第一个为 20，最后一个为 1。然后，对于每个参与者，我将接受他的排序，对于讲座 a，我将向每个相邻边添加位置值减去相对节点的位置值。

这个解释听起来有点不充分，让我们举个例子。有四个节点a、b、c、d。参与者按字母顺序排列它们。 1. 表示 20 分，2. -> 10 分，3. -> 5 分，4. -> 0 分。所以 a 和 b 之间的线将有 10 pts。 a 和 d 20 分之间。

此图表示讲座之间的关系。值越小，让两次讲座发生在不同时间就越重要。或者反过来，越高越好同时将它们放在不同的房间。

现在我们需要找到长度为 l 的最小 m 分离路径，以便为每个房间 mx 分配一组讲座。这很难(没有证据:))。现在是时候想出一个贪心算法来找到一些局部最小值了。我们可以使用例如 Kruscal 算法(或者更确切地说是 Prim 算法，因为图形将非常密集)来找到最小生成树，然后找到最小生成树。长度为 l 的路径。然后我们删除路径的节点，将它们分配给房间 m1。找到最小值。新图中的生成树。总共重复 m 次。

解决方案不一定是最优的，因为如果使用第一个最小路径的两条边构造它们，m 最小路径的总和可能会更低，因此算法将找不到最优解.

我对你的想法很感兴趣。