Мене завжди радувало помічати звичні фізичні явища в кілька абстрактних речах, типу алгоритмів та іншої математики. У цій статті ми розглянемо один з можливих способів пошуку блискавкою свого оптимального шляху.
Для початку згадаємо багатьом відомий SleepSort. Це алгоритм сортування чисел, але він сильно відрізняється від «традиційних» сортувань, таких як QuickSort або Mer^ Sort. Працює алгоритм так: давайте у відповідність кожному числу поставимо пропорційну затримку, потім запустимо для кожного числа потік, який буде чекати відведений час, а після виводити своє число. Нескладно зрозуміти, що числа будуть відсортовані за зростанням. Мене дуже забавляє це сортування, так як використовує в якості компаратора час, що рухається тільки вперед (у нашій моделі, у всякому разі).
А ще давайте згадаємо алгоритм Дейкстри. Багато хто в курсі що це, але все ж: це алгоритм пошуку мінімальних шляхів у графі з позитивними вагами ребер. Нехай A - безліч вершин, від якого ми хочемо шукати відстань. Результатом роботи алгоритму буде мінімальна відстань від цієї безлічі до кожної вершини і зазначення предка в мінімальному шляху.
Алгоритм простий:
- для безлічі A відповідь ясна (вона нульова, зі зрозумілих причин);
- отримання відповіді для ще однієї вершини: давайте шукати найближчу до початку вершину з сусідніх до безлічі вершин, відповідь для яких ясна, і запам'ятовувати для неї відповідь. Для них відстань знайти легко: воно складається з значення батьківської вершини і ваги з'єднуючого ребра. Реалізується це просто за допомогою підтримки мінімуму актуальним для кожної ітерації.
Нескладно довести, що відповіді побудовані таким чином будуть коректні.
А що буде, якщо ми будемо шукати найближчу вершину до початку за допомогою SleepSort? Можна уявити це так: пустимо «» воду, що розливається по графу «» таку, що вона проходить ребро за час пропорційного його ваги. «Розливати» її будемо від безлічі A. Тоді час від «» пуску води «» до досягнення деякої вершини (з безлічі сортованих вершин, а тільки їх вона і може досягти) буде якраз сумою часу досягнення попередньої і часу проходу ребра - це і є та характеристика, за якою ми хочемо сортувати вершини на кроці алгоритму Дейкстри (це SleepSort: "" вода дійшла "" це і є "sleep (prev + edge); вода дійди; ").
Очевидно, що "вода, що йде далі" "виконуватиме чергову ітерацію алгоритму: вона знову шукає найближчу вершину з околиці вже залитих вершин. І шлях, знайдений до якої-небудь вершини формально буде знайдений за алгоритмом Дейкстри.
Таким чином, стає ясно, що алгоритм Дейкстри «» фізичний до мозку кісток «».
На мою скромну думку, такі речі, як розряд (блискавка), шукають свій шлях саме таким способом, тобто алгоритмом Дейкстри + час, що йде вперед.
Неокірливе пояснення чому блискавка проходить через шлях найменшого опору
Може хто поправить, але я розумію це так: лідируючі заряди будуть поширюватися як у звичайному неоднорідному провіднику, а значить «струм» лідируючих зарядів по шляху мінімального опору буде максимальний (якщо представити як дуже велику кількість паралельних проводів в окресності кожної точки, цей результат виводиться з курсу шкільної фізики), а значить не буде нульовим, а значить далі на це місці буде розряд.
Сподіваюся, ця думка здалася цікавою знаючим людям, а новачкам допомогла ясніше представити роботу алгоритму.
