Contraction hierarсhies

Работа с графами достаточно часто встречается при разработке IT задач. Естественно есть список классических задач для которых существуют решения, продуманные и проверенные многими поколениями программ. А проблемы наступают, когда ограничения в мощностях начинают поджимать или объемы обрабатываемых данных зашкаливают за общепринятые нормы.

Для таких случаев приходиться искать обходные пути - далеко не всегда удачные и оптимальные. Вот и в моём случае XML с описанием графа, в запакованном виде (bz2) занимает порядка 7Gb, что не может не радовать. Найти расстояние между двумя точками этого графа, с учётом его нагруженности, стандартным алгоритмом Дейкстры (метод взрыва/растекания) является задачей, которая проваливает все ожидания спецификации и клиентов.
Выход нашелся совершенно неожиданно и в этот раз обеспечил такой задел, что даже неоптимальный код уровнем выше не может повлиять на состояние дел. Contraction hierarchies - экспериментальный алгоритм, разработанный кафедрой немецкого университета, который позволяет осуществлять поиск оптимального маршрута за сотни микросекунд(!) на графе, подобном описанному.
Алгоритм уже привлек внимание общественности, а программа, написанная студентом в чисто академических целях, как приложение к магистерской работе по данной тематике используется в Production системах более чем успешно. Более того, надо отдать должное человеку, не побоявшемуся взять неизвестный экспериментальный код за основу серьезного сервиса - это позволило сервису конкурировать на самых ранних этапах своего развития.

P.S. Учитесь учится, господа...

item