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

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

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

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

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

Мысль о структурах

Мысль о структурах

Разглядывал старый снимок, невесть когда сделанный зимой из вертолета. На снимке пойма реки в Западной Сибири, уже и не помню какой (если кто подскажет — буду благодарен). Но дело даже не в снимке и не в реке.

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

Нет, я не о гистограммах Шноля говорю. Это исследование удивительно и вызывает массу сомнений, особенно в части объяснения. Я скорее предполагаю, что в природной среде существуют структуры, устойчивость которых не зависит от их физической природы. Это может быть русло реки, ветвь дерева, сосулька, трещина — все что угодно, но при наличии определенной формы можно заранее предсказать дальнейшую динамику этой структуры. Нечто вроде планера из клеточного автомата Конвея.

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

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

Тут мысль переключается на алеатику и размышления Б.В. Гнеденко о природе вероятности, но пожалуй все это необходимо жестко пресечь. Тем более, только что вспомнил: этот снимок я сделал в ванной после того как лодку мыл.