一个规划工具的算法

Question

一个规划工具的算法

4

我正在编写一个小型软件应用程序，需要作为本地学校的简单规划工具。它要解决的“问题”相当基础。也就是说，教师需要与所有孩子的父母交谈。但是，有些孩子当然有不同分组中的兄弟姐妹，因此这些谈话需要安排在一起，以避免父母在晚上6点和晚上10点进行两次谈话的情况。因此，简而言之，给定一个n个孩子的集合，其中一些孩子有一个或多个兄弟姐妹，在一个日程安排中安排这些孩子的所有谈话。

现在，也许问题可以非常容易地解决，但另一方面，我有一种感觉，这可能是一个相当复杂的问题，需要并且可以通过某种算法解决。优雅地。但我对吗？有没有这样的算法？我已经查看了匈牙利算法，但它并不完全适用于这个特定的问题。

编辑：我忘记提到，所有谈话需要花费相同的时间。

谢谢！

- Razzie

4个回答

3

一种方法是使用声明性约束语言定义问题，然后让它为您解决问题。上次我使用的是ECLiPSe，这是一种巧妙的小语言，您可以通过约束来定义问题空间，然后让它找到满足这些约束的可允许值。

例如，我认为您有两类约束条件：

老师一次只能参加一个会议
同一家庭的所有学生必须连续安排时间

一旦您在ECLiPSe中定义了这些条件，它将计算出每个学生满足要求的值。如果您选择这种方法，还可以轻松添加需要的约束条件。例如，很容易说出老师在某个时间不可用，或者老师必须轮流进行行政工作等。

- Chris Pitman

哇，我不知道ECLiPSe，它看起来非常有趣！我可能会尝试一下！ - Razzie

1

这种排序感觉像一个“背包算法”类型的问题。你需要将家庭成员分组，然后适当地填充插槽。

如果你谷歌“背包算法”，你会看到足够的撰写来让你头晕目眩，还有一些好的编码解决方案。

- Kevin Buchan

2

背包问题在这里不适用。假设所有的会议都有足够的时间，或者会议时间将被缩短。即使如此，班级中只有一个孩子父母数量众多，也很容易填补所有时间。 - David Thornley

我思考背包问题的原因是因为这是现实世界，可能会有其他适用于某些教师/管理员的业务规则，这些规则可能会给不同的孩子施加权重。我想象一下，这可能会比仅仅用单个孩子填补剩余位置更加复杂。 - Kevin Buchan

Keving，我倾向于同意你的看法，因为我也认为它可能会变得更加复杂。有趣的是，我不确定，所以我可能需要在纸上写些东西。一位同事也提到了背包算法（虽然我认为它被称为背包问题算法）。+1 - Razzie

1

我认为，如果每个讲话都可以被归纳为“活动”，每个活动都有一个开始时间和结束时间，那么你可以使用计算机科学中研究过的活动选择算法。它基于贪心策略，可以在O(n)（其中n是活动数量）内解决。你可以在这里找到更多信息。我相信你需要在此进行预处理，以将兄弟/姐妹问题减少为同一类型的活动。

- Freddy

谢谢提供链接。快速浏览告诉我它至少与我的问题非常相关。我会仔细阅读。+1 - Razzie

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Henri · Accepted Answer

我认为这很容易。

首先将共享父母的孩子分组。在一个组内按顺序安排孩子，其余的随机排列。

另一种简化问题的方法是从父母的角度来看待问题，将兄弟姐妹视为“孩子”，给他们更多的时间。然后可以随机安排父母的时间表，但某些父母需要更多的时间（因为他们有多个孩子）。