Mishka> Теория расписаний/составление расписаний — это NP полная задача. А уж многокритериальная оптимизация расписания... Моща у компьютера очень быстро кончается.
Погоди, Дэвид Блейн
В общем случае, она таки реально NP. Но, как всегда, есть одно "но": при специальной топологии путей и схем составления поездов, она таки может быть сведена к "упаковке рюкзака". Про которую теперь уже известно, что она не NP.
Более того, мы ведь (теоретически) можем сделать такую топологию, что для неё возможны тривиальные решения. Я приведу реальный пример:
В своё время Xilinx была реальным лидером рынка FPGA (а ну-ка, кто вспомнит предыдущего?). Но у них компиляция проекта фактически сводилась к множественному поиску неконфликтующих путей. Парились они, парились, компилятор работал многие часы, да и то плотность набивки была так себе.
А потом вылезла Altera, и сказала: да ну пошло оно всё, мы будем делать по принципу телефонного коммутатора. И компилятор стал работать за минуты, и степень заполнения сразу выросла. Мой личный рекорд — 96%.
Вот, думается мне, и к паровозам можно что-то такое применить.