Предположим, есть N групп людей и M столов. Мы знаем размер каждой группы и вместимость каждого стола. Как нам подобрать людей к столам так, чтобы никакие два человека из одной и той же группы не сидели за одним и тем же столом?
Работает ли жадный подход для этой проблемы? (Жадный подход работает следующим образом: для каждого стола старайтесь «заполнить» его людьми из разных групп).
Матиас:
Я подозреваю, что работает следующий жадный подход: начиная с самой большой группы, берите каждую группу и распределяйте по одному человеку из этой группы за столом, выбирая первые столы с наибольшим количеством свободных мест.
Верно. И небольшая вариация рассуждения Тклечека доказывает это.
Допустим есть решение. Нам нужно доказать, что алгоритм находит решение в этом случае.
Это беспочвенно верно, если количество групп равно 0.
Для шага индукции мы должны показать, что если есть какое-либо решение, то есть такое, в котором один член самой большой группы сидит за каждым из (размер самой большой группы) самых больших столов.
Условие L: Для всех пар (T1,T2) столов, если T1 ‹ T2 и член самой большой группы сидит за T1, то другой член самой большой группы сидит за T2.
Пусть S1 — решение. Если S1 соответствует L, мы закончили. В противном случае существует пара (T1,T2) таблиц с T1 ‹ T2, такая, что член самой большой группы сидит в T1, но ни один член самой большой группы не сидит в T2. Поскольку T2 > T1, существует группа, в которой есть участник, сидящий в T2, но ни один в T1 (или есть свободное место в T2). Таким образом, эти двое могут поменяться местами (или член самой большой группы может переместиться на свободное место в T2), и мы получим решение S2 с меньшим количеством пар столов, нарушающих L. Так как существует только конечное число столов, после конечного числа шагов мы нашли решение Sk, удовлетворяющее L.
Гипотеза индукции: для всех созвездий N групп и всех чисел M таблиц, если есть решение, алгоритм найдет решение.
Теперь рассмотрим созвездие из (N+1) групп и M таблиц, для которых существует решение. В соответствии с вышеизложенным также существует решение, в котором члены наибольшей группы размещаются в соответствии с алгоритмом. Разместите их так. Это сводит задачу к разрешимому созвездию из N групп и M' таблиц, которое решается алгоритмом в соответствии с предположением индукции.
Предполагая, что группы и таблицы могут быть разного размера, я не думаю, что описанный жадный подход работает (по крайней мере, без дополнительных спецификаций). Предположим, у вас есть таблица из 2 T1 и таблица из 3 T2, а также 3 группы {A1}, {B1,B2} и {C1,C2}. Если я буду следовать вашему алгоритму, T1 получит {A1,B1}, и теперь у вас останутся T2 и {B2,C1,C2}, что не работает. Но есть решение T1 {B1,C1}, T2 {A1,B2,C2}.
Я подозреваю, что работает следующий жадный подход: начиная с самой большой группы, берите каждую группу и распределяйте по одному человеку из этой группы за столом, выбирая первые столы с наибольшим количеством свободных мест.
Работает следующий жадный подход:
Повторяйте следующие шаги, пока не останется мест:
Доказательство:
Нам просто нужно доказать, что после выполнения одного шага мы все еще можем прийти к оптимальному решению.
Назовем любого участника самой большой группы крутым парнем. Предположим, что существует другое оптимальное решение, в котором ни один крутой парень не сидит за самым большим столом. Давайте выберем любого человека, сидящего за самым большим столом в этом решении, и назовем его хромым парнем. Он должен принадлежать к группе размером не больше крутой группы. Итак, есть еще один стол, за которым сидит классный парень, но не хромой. Затем мы можем безопасно поменять местами хромого и крутого парня, что также приводит к оптимальному решению.
