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

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

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

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

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

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

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

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

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

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

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

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

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

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

🟡Arxiv
🟡Видео разбор

🎧 Perch 2.0 — AI, который слушает природу и спасает вымирающие виды.

DeepMind выпустили Perch 2.0 — компактную supervised-модель для биоакустики.

Без миллиардов параметров, без сложного self-supervised обучения — просто аккуратная модель, которая побила все бенчмарки и уже работает в полевых исследованиях.

🌱 Почему это важно
Звуки природы — это источник данных о биоразнообразии.
По аудиозаписям можно понять:
- какие животные живут в лесу,
- сколько их,
- размножаются ли они,
- не вытесняются ли они человеком.

Но расшифровка аудио — адский труд: в одном часе записи из тропиков десятки накладывающихся голосов.

🐦 Что умеет Perch 2.0
Perch 2.0 — универсальный эмбеддер для звуков животных.
Берёт 5 секунд аудио → выдаёт вектор, с которым можно:
- находить похожие записи,
- кластеризовать звуки,
- обучать простой классификатор для новых видов (few-shot).

⚡ Работает без GPU и без дообучения.

🛠 Архитектура
- Основa: EfficientNet-B3 (12M параметров).
- Три головы:
1. Классификация ~15k видов.
2. Прототипная — создаёт семантические логиты для distillation.
3. Source prediction — угадывает источник записи.
- Обучение в два шага:
1. Прототипная голова учится сама.
2. Её логиты становятся soft-label’ами для основной (**self-distillation**).

📊 Результаты
- SOTA на BirdSet и BEANS (ROC-AUC, mAP).
- Отличная переносимость на морских данных (киты, дельфины), которых почти не было в тренировке.
- Всё это — без fine-tuning, только фиксированные эмбеддинги.

Главный вывод
Perch 2.0 показывает, что:
🟢 качественная разметка,
🟢 простая архитектура,
🟢 чёткая постановка задачи
могут быть важнее, чем «бесконечные параметры» и сложные LLM.

🌍 Что это меняет
- Биологам — быстрый анализ джунглей Бразилии или рифов без написания своих моделей.
- ML-инженерам — наглядный пример, как обучать компактные сети без потери качества.
- Исследователям — напоминание: не всегда нужен GPT-4, чтобы сделать полезный инструмент.

🟠Github: https://github.com/google-research/perch-hoplite
🟠Подробнее: https://deepmind.google/discover/blog/how-ai-is-helping-advance-the-science-of-bioacoustics-to-save-endangered-species/
🟠Статья: https://arxiv.org/abs/2508.04665

@ai_machinelearning_big_data


#DeepMind #AI #Bioacoustics #MachineLearning #Perch #Ecology