Эвристика случайного поиска и теплоходы

[bminaiev]

А в данном конкретном случае разве не лучше перебрать все возможные варианты распределения групп по автобусам (если у нас 3 автобуса и 15 групп, то понадобиться перебрать всего лишь 3^15 = 14 * 10^6 вариантов)? Если точно вести функцию, описывающую «оптимальность» расстановки, то мы меньше чем за секунду (при данных ограничениях) получим самое лучшее решение.

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

[agorkov]

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

[StarMarine]

Для этой задачи рекомендую попробовать алгоритм имитации отжига (Simulated Annealing).

[BasicWolf]

Товарищи, а как же генетическая оптимизация?

[agorkov]

А как же отдых? И генетические алгоритмы для такой задачи по-моему излишни.

[optimizer]

почему так решили, кажется что трудоемкости больше? немало готовых программ, где сам генетический алгоритм уже реализован и только надо программировать постановку задачи в нотации ГА. Например вот программка Mendel 4

[pro100tak]

Время дипломных проектов на хабре :)

[vvzvlad]

программист на отдыхе. я так как-то случайно сервер настроил в египте.

[FINTER]

Потому что программист — это не профессия, это принцип жизни =)

[halyavin]

Для 3 автобусов по 50 человек + 20 групп получится 50^3*20=2500000=2.5e6 — динамическое программирование посчитает эту задачу без 3 пункта мгновенно. С третьим условием, если назначить, что неудачники — всегда последние группы, будет в несколько раз дольше. С 4 автобусами — нужно будет соптимизировать реализацию. От одного множителя 50 можно избавиться. Поскольку если мы рассмотрели k первых групп, то мы знаем сумму количества занятых мест.

[agorkov]

Да это понятно, но согласитесь, что написать случайное заполнение массива гораздо проще, чем манипулировать индексами в динамическом программировании.

[halyavin]

Динамическое программирование — простая штука. На написание графического интерфейса уйдет больше времени.