Мне всегда было приятно замечать знакомые физические явления в несколько абстрактных вещах, таких как алгоритмы и другая математика.
В этой статье мы рассмотрим один из возможных способов поиска молнии оптимального пути.
Для начала вспомним всем известный SleepSort. Это алгоритм сортировки чисел, но он сильно отличается от «традиционных» сортировок, таких как QuickSort или MergeSort. Алгоритм работает так: назначим каждому числу пропорциональную задержку, затем запустим для каждого числа поток, который будет ждать отведенное время, а затем выведем его номер.
Легко понять, что числа будут отсортированы по возрастанию.
Эта сортировка меня очень забавляет, потому что она использует время в качестве компаратора, перемещаясь только вперед (во всяком случае, в нашей модели).
Давайте также вспомним алгоритм Дейкстры.
Многие знают, что это такое, но всё же: это алгоритм поиска минимальных путей в графе с положительными весами ребер.
Пусть A — множество вершин, от которых мы хотим найти расстояние.
Результатом работы алгоритма будет минимальное расстояние от этого набора до каждой вершины и указание предка на минимальном пути.
Алгоритм прост:
- для множества A ответ очевиден (по понятным причинам он равен нулю);
- получение ответа для другой вершины: найдем ближайшую к началу вершину из соседних с множеством вершин, для которых ответ ясен, и запомним ответ для нее.
Для них расстояние найти легко: оно состоит из значения родительской вершины и веса соединяющего ребра.
Это реализуется просто путем поддержания минимума, релевантного для каждой итерации.
Что произойдет, если мы будем искать ближайшую к началу вершину с помощью SleepSort? Представить это можно так: давайте «прольем воду по графу» так, чтобы она прошла ребро за время, пропорциональное его весу.
Мы будем «лить» ее из множества А.
Тогда время от «запуска воды» до достижения определенной вершины (из множества отсортированных вершин, причем только тех, до которых она может дойти) будет в точности суммой времени достижения предыдущая и время прохождения ребра — это та характеристика, по которой мы хотим отсортировать вершины на шаге алгоритма Дейкстры (это SleepSort: «дошла вода» это «сон (prev+edge)» ; вода дошла;»).
Очевидно, что «вода, которая идет дальше», выполнит следующую итерацию алгоритма: она снова ищет ближайшую вершину из окрестности уже заполненных вершин.
И путь найден к какой-то вершине формально будет найден с помощью алгоритма Дейкстры.
Таким образом, становится ясно, что алгоритм Дейкстры «физичен до глубины души».
По моему скромному мнению, такие вещи, как молния, находят свой путь именно таким образом, то есть алгоритм Дейкстры + время вперед. Некоторые объяснения того, почему молния следует по пути наименьшего сопротивления Может быть, кто-то поправит, но я понимаю так: опережающие заряды будут распространяться как в обычном неоднородном проводнике, а значит, «ток» опережающих зарядов по пути минимального сопротивления будет максимальным (если представить себе очень большой количество параллельных проводов в окрестностях каждой точки, этот результат выведен из школьного курса физики), значит, он не будет равен нулю, а значит, в этом месте будет разряд. Надеюсь, что эта идея показалась знающим людям интересной, и помогла новичкам более четко представить себе работу алгоритма.
Теги: #Алгоритм Дейкстры #SleepSort #Алгоритмы
-
Сезам, Открой!
19 Oct, 24 -
Soft-Skills Успешного Тестировщика
19 Oct, 24 -
Ионный Ветер На Службе Охлаждения Чипов
19 Oct, 24
