Mathematical Models of the Real World

Новый алгоритм поиска кратчайшего пути на графе так называемый «барьер сортировки»

📌 Суть проблемы
Классические алгоритмы (например, Дейкстра) требуют сортировки вершин по расстоянию, чтобы выбрать ближайшую.
Сортировка — дорогая операция, особенно при больших графах.
С 1980-х считалось, что этот барьер невозможно преодолеть без потери универсальности.

🚀 Что предложил новый алгоритм? https://arxiv.org/abs/2504.17033?utm_source=Securitylab.ru
Вместо сортировки границы текущей области, алгоритм разбивает её на кластеры и выбирает по одному узлу из каждого.
Это снижает количество сравнений и устраняет необходимость сортировки.
Работает как для ориентированных, так и для неориентированных графов с произвольными весами.
Вдохновлён идеями Беллмана-Форда, но использует их точечно, чтобы выявить ключевые «узлы-связки».

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

Для чего это нужно:
🚗 1. Навигация и транспорт
GPS и карты: Google Maps, Waze и другие используют алгоритмы кратчайшего пути для построения маршрутов.
Логистика: Оптимизация доставки товаров, маршруты грузовиков, дронов и курьеров.
Транспортные сети: Расчёт времени поездки в метро, автобусах, авиаперелётах.
🖥 2. Компьютерные сети
Маршрутизация пакетов: Протоколы типа OSPF и BGP используют кратчайшие пути для передачи данных.
Оптимизация трафика: Балансировка нагрузки между серверами и дата-центрами.
🧬 3. Биология и медицина
Анализ молекулярных сетей: Поиск путей между генами, белками, метаболическими реакциями.
Медицинская диагностика: Сравнение симптомов и заболеваний через графы знаний.
🛒 4. Рекомендательные системы
Поиск связей между пользователями и товарами: Например, в Amazon или Netflix.
Социальные сети: Определение степени близости между людьми (например, «друзья друзей»).
🏙 5. Городское планирование и робототехника
Планирование движения роботов: В складских системах, на заводах.
Оптимизация инфраструктуры: Где строить дороги, мосты, электросети.
🎮 6. Игры и искусственный интеллект
Играющие агенты: Перемещение персонажей по карте.
AI-планирование: Принятие решений в стратегических играх.
На русском https://www.securitylab.ru/news/562195.php

arXiv.org

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is...

🔥4👍3

www.tgoop.com/MathModels/1284

1.6K viewsAug 10 at 10:55

Новый алгоритм поиска кратчайшего пути на графе так называемый «барьер сортировки»

📌 Суть проблемы
Классические алгоритмы (например, Дейкстра) требуют сортировки вершин по расстоянию, чтобы выбрать ближайшую.
Сортировка — дорогая операция, особенно при больших графах.
С 1980-х считалось, что этот барьер невозможно преодолеть без потери универсальности.

🚀 Что предложил новый алгоритм? https://arxiv.org/abs/2504.17033?utm_source=Securitylab.ru
Вместо сортировки границы текущей области, алгоритм разбивает её на кластеры и выбирает по одному узлу из каждого.
Это снижает количество сравнений и устраняет необходимость сортировки.
Работает как для ориентированных, так и для неориентированных графов с произвольными весами.
Вдохновлён идеями Беллмана-Форда, но использует их точечно, чтобы выявить ключевые «узлы-связки».

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

Для чего это нужно:
🚗 1. Навигация и транспорт
GPS и карты: Google Maps, Waze и другие используют алгоритмы кратчайшего пути для построения маршрутов.
Логистика: Оптимизация доставки товаров, маршруты грузовиков, дронов и курьеров.
Транспортные сети: Расчёт времени поездки в метро, автобусах, авиаперелётах.
🖥 2. Компьютерные сети
Маршрутизация пакетов: Протоколы типа OSPF и BGP используют кратчайшие пути для передачи данных.
Оптимизация трафика: Балансировка нагрузки между серверами и дата-центрами.
🧬 3. Биология и медицина
Анализ молекулярных сетей: Поиск путей между генами, белками, метаболическими реакциями.
Медицинская диагностика: Сравнение симптомов и заболеваний через графы знаний.
🛒 4. Рекомендательные системы
Поиск связей между пользователями и товарами: Например, в Amazon или Netflix.
Социальные сети: Определение степени близости между людьми (например, «друзья друзей»).
🏙 5. Городское планирование и робототехника
Планирование движения роботов: В складских системах, на заводах.
Оптимизация инфраструктуры: Где строить дороги, мосты, электросети.
🎮 6. Игры и искусственный интеллект
Играющие агенты: Перемещение персонажей по карте.
AI-планирование: Принятие решений в стратегических играх.
На русском https://www.securitylab.ru/news/562195.php

BY Mathematical Models of the Real World