2

我自愿编写一个程序来安排家​​长会。校长希望家长选择 3 个可能的日期时间来拜访他们的英语和数学老师（同时）。

一旦所有的家长都选择了 3 个约会时间，我应该找出安排家长会的最佳方式，以便尽可能多的家长与两位老师见面。

（如果有时间冲突，数学老师不能到会，家长只能和英语老师见面）

我对 NP 类型的问题了解不多，但是当我听到“最优”和“调度”这两个词时，我开始怀疑……

我已经告诉校长我不能这样做，但我想知道它是否是 NP 完全的。如果是，假设有：

  • 500名家长
  • 15名英语教师
  • 5位数学老师
  • 25 个日期时间可供选择

在你奶奶的电脑上，这可以在几秒钟、几分钟或几小时内正确解决吗？

4

1 回答 1

0

好吧，我对您的问题有部分答案，并且有一个模拟可以让我尝试不同的场景。这是我的工作（但可变）假设：

  • 参数与您列出的一样
  • 父母对会话时间的选择遵循幂律（本福德分布），因为它模拟了预期的偏好不均匀性
  • 根据运行情况，大约有 20 位家长“不妥协”，只能参加一次会议。
  • 每个英语老师都有一位且只有一位对应的数学老师，因为他们的相关性被认为很高，但我不知道有多高。该代码可以处理从 0 到 1 的任何相关系数。
  • 从生成似是而非的模拟父母（'smith' .. 'atkins'）、教师、时间选择和令人满意的结果的整个过程在一台中型机器（5300 BogoMIPS）上花费了 300 毫秒。

我的二阶优化甚至没有启动，因为第一遍允许每个家长的第一选择在一个会话中最多容纳 11 个家长。对于必须参加大约一半时间段且平均家长组约为 3 人的教师来说，这一结果并不理想。

如果有任何表达的兴趣，我可以提供代码，因为它大约有 125 行。

于 2010-08-20T04:57:28.380 回答