Forwarded from Machinelearning
Метод преодоления "барьера сортировки" для задач кратчайшего пути в ориентированных графах.
Группа исследователей из университетов Синьхуа, Стенфорда и Института Макса Планика представили детерминированный алгоритм для решения задачи SSSP в ориентированных графах с неотрицательными вещественными весами, который работает за время, пропорциональное числу ребер, умноженному на логарифмический множитель, который растет медленнее, чем обычный логарифм.
Проблема поиска кратчайшего пути от одной вершины до всех остальных (SSSP) — одна из фундаментальных в теории графов, и её история тянется с 50-х годов прошлого века. Классический алгоритм Дейкстры, в связке с продвинутыми структурами данных, решает эту задачу за время, которое примерно пропорционально сумме числа рёбер и произведения числа вершин на логарифм от их же числа.
Именно этот множитель - число вершин, умноженное на логарифм, долгое время считался теоретическим минимумом, так как в своей основе алгоритм Дейкстры побочно сортирует вершины по расстоянию от источника. Этот предел известен как «барьер сортировки» и казался непреодолимым.
Алгоритм Дейкстры на каждом шаге выбирает из "границы" - множества еще не обработанных вершин ту, что находится ближе всего к источнику. Это и создает узкое место, так как размер границы может достигать величины, сопоставимой с общим числом вершин в графе, и на каждом шаге требуется находить минимум.
Алгоритм Беллмана-Форда, в свою очередь, не требует сортировки, но его сложность пропорциональна числу ребер, умноженному на количество шагов, что слишком долго.
Вместо того чтобы поддерживать полную отсортированную границу, алгоритм фокусируется на ее сокращении. А если граница слишком велика, то запускается несколько шагов алгоритма Беллмана-Форда из ее вершин.
Это позволяет найти точное расстояние до некоторой части вершин, чьи кратчайшие пути коротки. Длинные же пути должны проходить через одну из "опорных" вершин, которых оказывается значительно меньше, чем вершин в исходной границе. Таким образом, сложная работа концентрируется только на этом небольшом наборе опорных точек.
Он рекурсивно разбивает задачу на несколько уровней. На каждом уровне применяется вышеописанная техника сокращения границы, что позволяет значительно уменьшить объем работы на каждую вершину, поскольку логарифмический множитель эффективно делится на другой, более медленно растущий логарифмический член.
В итоге, путем подбора внутренних параметров алгоритма, которые являются специфическими функциями от логарифма числа вершин, и достигается итоговая временная сложность, пропорциональная числу ребер, умноженному на этот новый, более медленно растущий логарифмический множитель.
— Быстрее решаются задачи в навигации, графах дорог, сетях и планировании.
— Доказано, что Дейкстра — не предел, и можно ещё ускорять поиск кратчайших путей.
@ai_machinelearning_big_data
#AI #ML #Sorting #Graphs #Algorithm
Please open Telegram to view this post
VIEW IN TELEGRAM
👍14🔥5❤2😐2
Forwarded from Machinelearning
Главный вывод из пятого ежегодного списка Top 100 AI Apps — экосистема ИИ начинает приходить в равновесие.
В веб-рейтинге появилось всего 11 новых имен, что заметно меньше, чем было мартовском отчете. В мобильном сегменте, напротив, новичков больше — целых 14, но это связано с тем, что App Store активно вычищают "клонов ChatGPT", освобождая место для оригинальных приложений.
Их флагманский ассистент Gemini занял 2 место после ChatGPT и в вебе, и на мобильных устройствах. Правда, разрыв пока существенный: в вебе Gemini набирает примерно 12% от трафика ChatGPT. А вот на мобильных платформах ситуация иная - у Gemini уже почти половина ежемесячно активных пользователей ChatGPT.
Интересная деталь: почти 90% мобильной аудитории Gemini сидит на Android, тогда как у ChatGPT доля Android-пользователей составляет 60%.
Помимо Gemini, в топ-10 ворвался Google AI Studio. Следом идeт NotebookLM на 13-м месте, а экспериментальная площадка Google Labs заняла 39-ю строчку, получив в мае 2025 года прирост трафика более чем на 13% после запуска видеомодели Veo 3.
Grok занял четвeртое место в вебе и 23-е на мобильных. Его мобильный рост особенно впечатляет: с нуля в конце 2024 года до более чем 20 миллионов MAU сейчас. В июле 2025 года, после релиза модели Grok 4, использование приложения подскочило почти на 40%.
У Марка Цукербкрга успехи скромнее: 46-е место в вебе и полное отсутствие в мобильном топе.
Perplexity продолжает уверенно расти, а вот Claude и DeepSeek показывают смешанные результаты. DeepSeek особенно сильно просел в вебе, потеряв более 40% трафика со своего пика в феврале 2025 года.
Сразу 3 компании, ориентированные на внутренний рынок, вошли в топ-20 веб-рейтинга: Quark от Alibaba (№9), Doubao от Bytedance (№12) и Kimi от Moonshot AI (№17). Более 75% их трафика приходится на Китай, где доступ к ChatGPT или Claude ограничен.
Ещё более поразительна картина на мобильных устройствах. По оценкам, 22 из 50 приложений в топе были разработаны в Китае, но используются преимущественно за его пределами. Особенно сильна их концентрация в категории "фото и видео": одна только компания Meitu представлена 5-ю продуктами, включая BeautyPlus и Wink. Bytedance также не отстаёт с ассистентами Doubao и Cici.
Это ChatGPT, Civitai, Poe, Perplexity, LeonardoAI, VEED, Gamma, QuiliBot, CutOut, Character AI, Midjourney, Photoroom, Eleven Labs и HuggingFace.
Из этой "звёздной" команды только 5 компаний разрабатывают собственные модели, 7 используют сторонние API или опенсорс-решения, а 2 являются агрегаторами моделей.
@ai_machinelearning_big_data
#news #ai #ml
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
👍6🔥3❤2