📌Новый прорыв в алгоритмах: найден способ считать кратчайшие пути быстрее Дейкстры

Метод преодоления "барьера сортировки" для задач кратчайшего пути в ориентированных графах.

Группа исследователей из университетов Синьхуа, Стенфорда и Института Макса Планика представили детерминированный алгоритм для решения задачи SSSP в ориентированных графах с неотрицательными вещественными весами, который работает за время, пропорциональное числу ребер, умноженному на логарифмический множитель, который растет медленнее, чем обычный логарифм.

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

Именно этот множитель - число вершин, умноженное на логарифм, долгое время считался теоретическим минимумом, так как в своей основе алгоритм Дейкстры побочно сортирует вершины по расстоянию от источника. Этот предел известен как «барьер сортировки» и казался непреодолимым.

🟡Основная идея работы - гибрид из алгоритма Дейкстры и алгоритма Беллмана-Форда.

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

Алгоритм Беллмана-Форда, в свою очередь, не требует сортировки, но его сложность пропорциональна числу ребер, умноженному на количество шагов, что слишком долго.

🟡Новый подход использует рекурсию.

Вместо того чтобы поддерживать полную отсортированную границу, алгоритм фокусируется на ее сокращении. А если граница слишком велика, то запускается несколько шагов алгоритма Беллмана-Форда из ее вершин.

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

🟡Принцип "разделяй и властвуй".

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

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

✔️ Зачем это нужно
— Быстрее решаются задачи в навигации, графах дорог, сетях и планировании.
— Доказано, что Дейкстра — не предел, и можно ещё ускорять поиск кратчайших путей.


🟡Arxiv


@ai_machinelearning_big_data

#AI #ML #Sorting #Graphs #Algorithm

📌Python на взлете, а Python Software Foundation в минусе на 1.5 млн. долларов: разбираем свежий опрос.

Python Software Foundation (PSF) совместно с JetBrains опубликовала результаты восьмого, самого крупного в истории опроса разработчиков - в нём приняли участие более 30 000 человек.

Данные, собранные в конце 2024 года, показывают, что 72% респондентов используют Python в рабочих целях и это подтверждает доминирующую роль языка в индустрии. И популярность Python продолжает расти: согласно другому исследованию, от Stack Overflow, использование языка увеличилось на 7%.

🟡Приток свежей крови в экосистему.

Половина опрошенных имеют менее 2 лет профессионального опыта в программировании, а 39% начали использовать Python в течение последних 2 лет. Это говорит о том, что язык активно привлекает новичков и остается ключевой точкой входа в разработку.

🟡Парадокс версий.

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

Однако сами разработчики не торопятся: 53% заявляют, что текущая версия полностью удовлетворяет их потребности, 27% ссылаются на проблемы с совместимостью, а 25% - на нехватку времени.

При этом нельзя сказать, что сообщество инертно. Самая популярная версия - 3.12 (35%), выпущенная в конце 2023 года, за ней следует 3.11 (21%), что говорит о довольно быстрой адаптации к не самым последним, но свежим релизам.

🟡Сферы применения.

Анализ данных (48%) и веб-разработка (46%) идут практически вровень. Но если к анализу прибавить ML (41%) и инжиниринг данных (31%), то доминирование Data Science становится очевидным.

В мире веб-фреймворков происходит смена караула: FastAPI (38%) резко вырвался вперед, обогнав ветеранов: Django (35%) и Flask (34%). Год назад у FastAPI было всего 29%.

Ещё один стремительный взлёт — у написанного на Rust менеджера пакетов uv, который позиционируется как замена pip. Заявляя о кратном превосходстве в скорости, он уже отхватил 11% пользователей.

А вот в лагере IDE плохие новости для спонсора опроса, JetBrains: Visual Studio Code укрепил свое лидерство, набрав 48% (против 41% в прошлом году), а доля PyCharm снизилась до 25% (с 31%).

🟡Финансовые проблемы Python Software Foundation.

Ранее в этом месяце PSF объявила о приостановке своей грантовой программы из-за нехватки средств.

Годовой отчет за 2024 год показал чистый убыток в размере 1 462 000 долларов, что значительно больше, чем в 2023 году, там убыток был 225 000 долларов.

Фонд, который поддерживает репозиторий PyPI, дистрибуцию самого Python и нанимает разработчиков для CPython, оказался в сложной ситуации и явно нуждается в большей поддержке и ресурсах от корпораций, которые строят свой бизнес и получают доход на Python.


@ai_machinelearning_big_data

#news #ai #ml