算法的一个规划工具

Question

我正在写一个小型的软件应用程序，需要作为一个简单的规划工具，为本地学校。'问题'，它需要解决的是相当基本的。即，教师需要跟父母的所有儿童。然而，有些儿童，当然，兄弟和姐妹在不同的组，因此这些谈判需要定下来分开，以避免的情况是父母谈谈至下午6时，另一个在10点。因此，在短期、定的集合 n 儿童，其中一些儿童有1个或更多的兄弟或姐妹，产生一个时间表，所有的会谈，这些儿童是有计划彼此相邻。

现在，也许可解决上述问题非常容易的，但在其他的我有一种感觉，这可能是一个相当复杂的问题，即需要的和可以解决与某种形式的算法。优雅。但我说的对吗?是那里吗？我看了看 匈牙利 alorithm但它并不完全适用于这个特别的问题。

编辑：我忘了说了，所有的会谈中采取同样的时间量。

谢谢！

Answer 1

我觉得这是很容易的。

首先组，因为它们共享父母属于一起的孩子。调度组内的儿童连续，调度其余为随机的。

另一种方法是抽象的它，使问题更容易是从父母的角度看，看到兄弟姐妹为“孩子”，给他们更多的时间。然后，你可以安排父母在随机的，但有些需要更多的时间（因为他们有多个childeren）。

Answer 2

一种办法竟dbe定义的问题，在一个声明约束的语言，然后让它解决你的问题。我最后一次这样做，我用的 日食, ，这是一个漂亮的小语的定义问题空间的约束，然后让它找到允许的价值，满足这些制约因素。

例如，我相信您有两种类的制约因素：

1. 老师可能只有一个 会议在一段时间
2. 所有的学生在同一个家庭必须 已经连续的时隙

一旦你限定这些在日食时，它将计算数值为每个学生满足要求。如果你走这条路，你也可以很容易地加限制，因为您需要。例如，很容易说教是不可用的时隙Y或教师必须采取实证明做行政工作，等等。

Answer 3

此排序感觉就像一个“背包算法”类型的问题。需要组的家庭成员一起然后适当地填充槽。

如果你谷歌“背包算法”，你会看到足够写UPS，使你的头旋，也有一些很好的编码解决方案。

Answer 4

我想，如果每个通话可以减少到“活动”，每个活动都有一个起始时间，你可以使用在计算机科学的研究活动选择算法的结束时间。它是基于一种贪婪的做法，并可能在O（n）（其中n是活动的数量）来解决。你可以找到更多信息这里。我相信你将需要有在这里做一个预处理，以便能够减少哥哥/姐姐的问题，因为同类型的活动。