Pull to refresh

Алгоритм Дейкстры и физика

Reading time 2 min
Views 19K
Меня всегда радовало замечать привычные физичные явления в несколько абстрактных вещах, типа алгоритмов и прочей математики. В этой статье мы рассмотрим один из возможных способов поиска молнией своего оптимального пути.

Для начала вспомним многим известный SleepSort. Это алгоритм сортировки чисел, но он сильно отличается от «традиционных» сортировок, таких как QuickSort или MergeSort. Работает алгоритм так: давайте в соответствие каждому числу поставим пропорциональную задержку, потом запустим для каждого числа поток, который будет ждать отведённое время, а после выводить своё число. Несложно понять, что числа будут отсортированны по возрастанию. Меня очень забавляет эта сортировка, так как использует в качестве компаратора время, движущееся только вперёд (в нашей модели, во всяком случае).

А ещё давайте вспомним алгоритм Дейкстры. Многие в курсе что это, но все же: это алгоритм поиска минимальных путей в графе с положительными весами рёбер. Пусть A — множество вершин, от которого мы хотим искать расстояние. Результатом работы алгоритма будет минимальное расстояние от этого множества до каждой вершины и указание предка в минимальном пути.

Алгоритм прост:
  1. для множества A ответ ясен (он нулевой, по понятным причинам);
  2. получение ответа для еще одной вершины: давайте искать ближайшую к началу вершину из соседних к множеству вершин, ответ для которых ясен, и запоминать для неё ответ. Для них расстояние найти легко: оно складывается из значения родительной вершины и веса соединяющего ребра. Реализуется это просто при помощи поддержки минимума актуальным для каждой итерации.

Несложно доказать, что ответы построенные таким образом будут корректны.

А что будет, если мы будем искать ближайшую вершину к началу при помощи SleepSort? Можно представить это так: пустим "воду, разливающуюся по графу" такую, что она проходит ребро за время пропорциональное его весу. «Разливать» ее будем от множества A. Тогда время от "пуска воды" до достижения некоторой вершины (из множества сортируемых вершин, а только их она и может достигнуть) будет как раз суммой времени достижения предыдущей и времени прохода ребра — это и есть та характеристика, по которой мы хотим сортировать вершины на шаге алгоритма Дейкстры (это SleepSort: "вода дошла" это и есть «sleep (prev + edge); вода дойди;»).

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

Таким образом, становится ясно, что алгоритм Дейкстры "физичен до мозга костей".

По моему скромному мнению, такие вещи, как разряд (молния), ищут свой путь именно таким способом, то есть алгоритмом Дейкстры + идущее вперёд время.

Неокоторое объяснение почему молния проходит через путь наименьшего сопротивления
Может кто поправит, но я понимаю это так: лидирующие заряды будут распространятся как в обычном неоднородном проводнике, а значит «ток» лидирующих зарядов по пути минимального сопротивления будет максимален (если представить как очень большое количество параллельных проводов в окресности каждой точки, этот результат выводится из курса школьной физики), а значит не будет нулевым, а значит далее на это месте будет разряд.


Надеюсь, эта мысль показалась интересной знающим людям, а новичкам помогла яснее представить работу алгоритма.
Tags:
Hubs:
+11
Comments 3
Comments Comments 3

Articles