задача о составлении расписания

From

Andrey Govorov (2:5058/16.14)

To

George Shepelev ()

Date

2000-01-18T01:44Z

Area

RU.ALGORITHMS

Hello George!

Sunday January 16 2000 22:44, George Shepelev wrote to Konstantin Polyakov:
 GS>>> Универсальный приём на такой случай - полный перебор.
 GS>>> Перебираешь варианты расписаний, считаешь их "веса". Сохраняешь
 GS>>> номер варианта с наибольшим "весом"...
 KP>> Не надо сбивать людей с толку. В pеальных задачах (когда,
 KP>> напpимеp, в школе 20-30 классов и 50-60 учителей) полный пеpебоp
 KP>> - это тупик.
 GS>   Не забывай с какой скоростью апгрейдятся компьютеры.
 GS> Очень может оказаться, что к тому времени, когда ты найдёшь
 GS> "математическое" решение - задачу давно решат перебором...

Классический пример - задача коммивояжера. При размерности примерно 50 пунктов решается за время -> бесконечность при современной мощности компьютеров. Не думаю что скорость апгрейда компьютеров будет стремиться туда же.

Andrey

--- GoldED/386 2.50+
 * Origin: Много говорить - вредно... (2:5058/16.14)