Перколяция в роутинге

Оказывается, если ложиться спать не после рассвета, а в семь вечера, то просыпаться в пять утра значительно легче. А еще, оказывается, что среди докладов и статей о картографии, почти не упоминается теория перколяции. Но если о первом можно догадаться, хотя-бы теоретически, причины второго мне совершенно не ясны.

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

Никогда не поверю, что на развитии алгоритма Дейкстры все остановилось. В чем причина? В иной терминологии? В специфике задач? Или может, реальность такова, что любая разновидность модели Шкловского — де Жена оказывается бесполезной? Даже если так, все-равно кого-то должна была соблазнить идея рассматривать построение связного графа в качестве фазового перехода.

Тема безгранична для теории и практики картографов-урбанистов. Особенно, если представить дорожную сеть как набор ламинарных и хаотических участков. Введя ограничение на максимальную протяженность маршрута, вы получите области в которых небольшое отклонение от маршрута ведет к невозможности его завершения. Значит можно рассчитать размерность Хаусдорфа-Безиковича для фазового пространства дорожной сети. Я только не понимаю, что такая размерность будет означать и как ее рассчитывать. Но это все-равно интереснее инструкции по установке графхоппера.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *