Comments 12
А в данном конкретном случае разве не лучше перебрать все возможные варианты распределения групп по автобусам (если у нас 3 автобуса и 15 групп, то понадобиться перебрать всего лишь 3^15 = 14 * 10^6 вариантов)? Если точно вести функцию, описывающую «оптимальность» расстановки, то мы меньше чем за секунду (при данных ограничениях) получим самое лучшее решение.
P. S. я не в коем случае не пытаюсь сказать, что эвристические алгоритмы не нужны, только, что в данном случае можно обойтись без них (перебор всех вариантов пишется явно быстрее чем эти эвристики).
P. S. я не в коем случае не пытаюсь сказать, что эвристические алгоритмы не нужны, только, что в данном случае можно обойтись без них (перебор всех вариантов пишется явно быстрее чем эти эвристики).
Для этой задачи рекомендую попробовать алгоритм имитации отжига (Simulated Annealing).
Товарищи, а как же генетическая оптимизация?
Время дипломных проектов на хабре :)
программист на отдыхе. я так как-то случайно сервер настроил в египте.
Для 3 автобусов по 50 человек + 20 групп получится 50^3*20=2500000=2.5e6 — динамическое программирование посчитает эту задачу без 3 пункта мгновенно. С третьим условием, если назначить, что неудачники — всегда последние группы, будет в несколько раз дольше. С 4 автобусами — нужно будет соптимизировать реализацию. От одного множителя 50 можно избавиться. Поскольку если мы рассмотрели k первых групп, то мы знаем сумму количества занятых мест.
Sign up to leave a comment.
Эвристика случайного поиска и теплоходы