В этом сообщении блога мы обсудим проблему организации детей в группы. И вы узнаете, что если вы используете наивный алгоритм для решения этой проблемы, он будет работать очень и очень медленно, потому что время работы этого алгоритма экспоненциально. Позже мы обсудим, как значительно сократить время обучения, придумав алгоритм с полиномиальным временем.

Рассмотрим следующую ситуацию. Вы пригласили много детей на вечеринку и хотите их развлечь, а также чему-то научить. Вы собираетесь нанять несколько учителей, разделить детей на группы и назначить учителя в каждую из групп, этот учитель будет работать с этой группой на протяжении всей партии.

Но вы знаете, что для того, чтобы учитель мог эффективно работать с группой детей, дети этой группы должны быть примерно одного возраста. В частности, возраст любых двух детей в одной группе должен отличаться максимум на один год.

Кроме того, вы хотите минимизировать количество групп. Потому что вы хотите нанимать меньше учителей и тратить деньги на подарки и другие развлечения для детей. Итак, вам нужно разделить детей на минимально возможное количество групп. Таким образом, возраст любых двух детей в любой группе различается не более чем на один год.

Теперь давайте посмотрим на псевдокод наивного алгоритма, решающего эту проблему.

По сути, этот алгоритм будет рассматривать все возможные разбиения детей на группы и находить такое разбиение, которое удовлетворяет тому свойству, что возраст детей в любой группе должен отличаться не более чем на единицу, и содержит минимальное количество групп.

Мы начинаем с присвоения начального значения количества групп ответу m, и это начальное значение - просто количество детей. Потому что мы всегда можем разделить всех детей на группы по одному, и тогда, конечно, в каждой группе будет только один ребенок, поэтому условие выполняется.

Затем мы рассматриваем всевозможные варианты разделения всех детей на группы. Количество групп может быть переменным, поэтому это обозначается числом k, и у нас есть группы G1, G2 и до Gk.

И затем у нас есть раздел, нам сначала нужно проверить, хороший ли он или нет. Итак, у нас есть переменная good, которой мы изначально присвоили значение true, потому что мы думаем, что, возможно, этот раздел будет хорошим. Но затем нам нужно проверить для каждой группы, удовлетворяет ли она нашему условию или нет. Итак, мы переходим a для группы с индексом i группы от 1 до k, а затем мы рассматриваем конкретную группу GI, и нам нужно определить, все ли дети в этой группе отличаются не более чем на 1 год, или есть двое детей, которые больше различаются.

Чтобы убедиться в этом, достаточно сравнить самого младшего ребенка со старшим. Если их возраст отличается более чем на единицу, значит, группа плохая. В противном случае каждые двое детей различаются максимум на один год, так что группа хороша. Итак, мы перебираем все группы в цикле for. Если хотя бы одна из групп плохая, то в конце наша переменная good будет содержать значение false. В противном случае все группы хороши, и переменная good будет содержать значение true. Итак, после этого цикла for мы проверяем значение переменной good и, если оно истинно, улучшаем наш ответ. По крайней мере, попробуйте его улучшить. С минимальным его текущим значением и количеством групп в текущем разделе. Итак, к концу внешнего цикла for, который проходит через все разделы, наша переменная m будет содержать минимально возможное количество групп в разделе, удовлетворяющем всем условиям. Очевидно, что этот алгоритм работает правильно, поскольку он в основном рассматривает все возможные варианты и выбирает лучший из всех вариантов, удовлетворяющих нашему условию о группах.

Теперь оценим время работы этого алгоритма.

И я утверждаю, что количество операций, которые выполняет этот алгоритм, составляет по крайней мере 2 в степени n, где n - количество дочерних элементов в C. На самом деле этот алгоритм работает намного медленнее и выполняет гораздо больше операций, чем 2 в степени n, но мы просто докажем эту нижнюю границу, чтобы показать, что этот алгоритм очень медленный.

Чтобы доказать это, давайте рассмотрим разделение детей на две группы. Конечно, разделов гораздо больше. Мы можем разделить их на два, три, четыре и так далее. Намного больше групп. Но давайте просто рассмотрим разбиения на две группы и докажем, что даже таких разбиений уже не меньше двух в степени n. На самом деле, если C является объединением двух групп, G1 и G2, то в принципе мы можем сделать такое разбиение для любого G1, который является подмножеством такого C всех дочерних групп. Для любого G1 просто сделайте группу G2, содержащую всех детей, не входящих в первую группу. И тогда все дети будут разделены на эти две группы. Итак, теперь размер набора всех детей равен n.

И если вы хотите вычислить количество возможных групп G1, мы должны отметить, что каждый элемент набора или каждый дочерний элемент может быть либо включен, либо исключен из группы G1. Значит, может быть 2 в степени n различных групп G1. Итак, есть по крайней мере 2 в степени n разбиений множества всех детей в две группы. и это означает, что наш алгоритм выполнит не менее 2 операций в степени n, поскольку при этом учитываются все разделы. Среди всех перегородок есть все перегородки на две группы.

Итак, как долго это действительно будет работать? Мы видим, что алгоритм Naive работает за время Omega (2n), поэтому он делает не менее 2 в степени n операций. И, например, всего для 50 детей это будет как минимум 2 в степени 50 или наибольшее число, указанное на слайде. Это количество операций, которые нам нужно будет выполнить, и я предполагаю, что на обычном компьютере вам потребуется не менее двух недель, чтобы вычислить это, если это было именно то количество операций, которое вам нужно. Так что это работает очень, очень медленно …….