Введение
В алгоритмах, как и в жизни, негатив может быть помехой.
Рассмотрим задачу поиска кратчайшего пути между двумя точками на графе — сети узлов, соединенных ссылками или ребрами. Часто эти ребра не взаимозаменяемы: граф может представлять дорожную карту, на которой некоторые дороги медленнее других или требуют более высоких сборов. Ученые-компьютерщики объясняют эти различия, сопоставляя каждому ребру «вес», который количественно определяет стоимость перемещения по этому сегменту — независимо от того, представляет ли эта стоимость время, деньги или что-то еще. С 1950-х годов они знали, как находить кратчайшие пути практически настолько быстро, насколько это теоретически возможно, предполагая, что все веса являются положительными числами.
Но на некоторых графах веса могут быть отрицательными — перемещение по одному сегменту может компенсировать стоимость прохождения другого. Рассмотрим, например, водителя службы доставки, который должен сбалансировать стоимость бензина и дорожных сборов (представленные положительными весами) с доходом от перевозки посылок (представленными отрицательными весами). В таких случаях самый быстрый из известных алгоритмов поиска кратчайшего пути не работает. В течение десятилетий быстрые алгоритмы поиска кратчайших путей на графах с отрицательным весом оставались неуловимыми.
Теперь трое ученых-компьютерщиков решили эту давнюю проблему. Их новый алгоритм, который находит кратчайшие пути через граф от заданного «исходного» узла к любому другому узлу, почти соответствует скорости, достигнутой алгоритмами с положительным весом так давно.
Более того, новый подход использует математические методы десятилетней давности, избегая более сложных методов, которые доминируют в современных исследованиях теории графов.
«Я просто не мог поверить, что существует такой простой алгоритм», — сказал Максимилиан Пробст Гутенберг, ученый-компьютерщик из Швейцарского федерального технологического института в Цюрихе. «Все это существует уже 40 лет. Просто нужно, чтобы кто-то был очень умным и полным решимости заставить все это работать».
Пределы жадности
История начинается в 1956 году, когда голландский ученый Эдсгер Дейкстра разработал быстрый алгоритм для поиска кратчайших путей на графе только с положительными весами. Чтобы понять это, представьте, что вы начинаете с источника и исследуете граф по одному узлу за раз, записывая веса вновь обнаруженных ребер по мере продвижения. Каждый раз, когда вы посещаете узел, делайте предварительные оценки кратчайших путей от источника к каждому из соседей нового узла, обновляя любые существующие оценки, если вы нашли новый более короткий путь. Чтобы решить, какой неизведанный узел посетить следующим, используйте так называемую жадную стратегию: перейдите к тому, что находится ближе всего к источнику в соответствии с вашей текущей оценкой.
С положительными весами путь, по которому алгоритм Дейкстры посещает каждый узел в первый раз, действительно является кратчайшим. Легче всего увидеть, что это верно для самого первого шага. Представьте себе два узла A и B, соединенных ребром с весом 2. Если A является исходным узлом, а каждое другое касающееся его ребро имеет больший вес, то прямой путь от A до B должен быть кратчайшим из возможных путей, соединяющих эти две точки. , так как первый сегмент любого другого пути уже был бы длиннее. Подобные рассуждения работают на каждом шаге. Алгоритму никогда не приходится оглядываться назад, поэтому он гарантированно завершится после одного прохода по графу — вот что делает его таким быстрым.
Но отрицательные веса создают проблемы для жадной стратегии Дейкстры. Рассмотрим еще раз нашего водителя доставки. Прямой маршрут из А в Б, дающий небольшую прибыль, может принести меньше денег, чем окольный путь, который где-то дает большую отдачу. «Вы не можете принимать решения только на основе местной информации», — сказал Санджив Кханна, ученый-компьютерщик из Пенсильванского университета. «Возможно, вам придется сделать несколько, казалось бы, неоптимальных ходов, чтобы наконец получить настоящую награду».
На протяжении десятилетий компьютерщики, работающие над графами с отрицательным весом, пытались сопоставить скорость алгоритма Дейкстры с аналогичными «комбинаторными» алгоритмами. Они включают в себя дискретные операции, такие как подсчет возможностей, изменение весов и выборочное удаление ребер, которые отражают дискретную структуру базового графа. Однако к 1990-м годам прогресс замедлился. Совсем недавно исследователи использовали алгоритмы «непрерывной оптимизации», которые заимствуют приемы исчисления. К сожалению, полученное в результате ускорение было ограничено и часто достигалось за счет простоты.
Разорвать цикл
Летом 2021 года двое ученых-компьютерщиков, ставших коллегами в Копенгагенском университете, — Данупон Нанонгкай и Кристиан Вульф-Нильсен — искали тему для совместного исследовательского проекта. «Кристиан сказал: «О, кстати, я был в отпуске и поэтому пытался придумать что-то очень амбициозное», — вспоминает Нанонгкай, который сейчас работает в Институте информатики Макса Планка в Саарбрюкене, Германия. Они остановились на задаче о кратчайших путях с отрицательным весом и предложили Аарон Бернштейн Университета Рутгерса, чтобы присоединиться к ним.
Все три исследователя были экспертами в алгоритмах комбинаторных графов для решения других задач, и они хотели увидеть, как далеко могут продвинуться эти относительно древние подходы. «На самом деле есть определенная свобода в работе над амбициозной проблемой, которая была открыта в течение длительного времени», — сказал Бернстайн.
Троица начала с временного игнорирования подмножества возможных графов, содержащих отрицательные циклы. Это пути, которые возвращаются туда, где они начались, после прохождения ряда ребер, веса которых в сумме дают отрицательное число. В графе с отрицательными циклами, достижимыми из начальной точки, понятие кратчайшего пути не работает, поскольку вы можете сделать расстояние до любого узла как отрицательным (или выгодным), как вам нравится, совершая повторные круги вокруг отрицательного цикла, прежде чем отправляясь к месту назначения.
Исследователи подозревали, что именно длинные отрицательные пути в основном усложняют задачу. Поэтому они начали сосредотачиваться на тесных кластерах соседних узлов, которые не могут содержать длинных отрицательных путей: это потому, что если две точки соединены коротким положительным путем, добавление длинного отрицательного пути между ними создаст отрицательный цикл. В тесном кластере «тот факт, что все находятся близко друг к другу в положительном смысле, на самом деле дает вам полезную информацию и об отрицательных сторонах», — сказал Бернстайн. «Это говорит вам, что вещи не могут быть слишком негативными».
Большинство графов содержат множество таких сплоченных кластеров, слабо связанных друг с другом. Если бы исследователи могли точно определить все кластеры, они подозревали, что могли бы разработать способ быстрого поиска кратчайших путей внутри каждого из них. Оттуда им может быть проще соединить отдельные кластеры и найти кратчайшие пути на исходном графе. Но для этого потребовалось бы быстро определить области любого графа, в которых узлы расположены близко друг к другу, а они не знали, как это сделать. Ключом оказалась техника, возникшая в совершенно другой области теории графов.
Разрезание графиков
В 1980-х годах ученые-компьютерщики разработали технику, называемую декомпозицией малого диаметра, для выделения тесных кластеров в графе и определения ребер, которые необходимо удалить, чтобы разделить эти кластеры. Этот метод позволяет разделить графики на независимые участки. Он был изобретен для облегчения «распределенных» алгоритмов, в которых вычисления выполняются параллельно в разных частях графа, поэтому он был менее полезен для алгоритмов поиска кратчайших путей, не обладающих этим свойством.
Бернстайн, Нанонгкай и Вульф-Нильсен поняли, что разложение малого диаметра может помочь им идентифицировать кластеры без особого концентрированного негатива. К сожалению, стандартные алгоритмы декомпозиции малого диаметра работают только с неориентированными графами, в которых каждое ребро можно пройти в обоих направлениях. Тем временем проблема кратчайших путей с отрицательным весом имеет смысл только на ориентированных графах, в которых каждое ребро является улицей с односторонним движением. (В противном случае одно ненаправленное отрицательное ребро создало бы отрицательный цикл, состоящий из повторяющихся переходов туда и обратно через это ребро.) Если исследователи хотели использовать разложение с малым диаметром, им пришлось бы адаптировать его.
Именно это они и сделали в своей новой газете. Вдохновленный прошлая работа в котором Бернштейн и Вульф-Нильсен сотрудничали с Пробстом Гутенбергом, они разработали процедуру разрушения ориентированных графов, аналогичную разложению малого диаметра. Процедура разбивает произвольный ориентированный граф на серию тесно связанных кластеров, используя случайный процесс для удаления всего нескольких ребер. После этого эти кластеры соединяются более разреженной сетью, в которой все ребра указывают в одном направлении. Такая сеть называется ориентированным ациклическим графом или DAG.
Думайте о DAG как о потоке, в котором вода может течь по разным путям: некоторые пути втекают из разных источников, другие разветвляются в разных направлениях, а третьи могут разделяться и снова сливаться. Но ничто никогда не течет назад, так что циклов нет; это значительно упрощает работу с DAG.
Исследователи давно знают, как быстро находить кратчайшие пути на DAG даже с отрицательными весами. Таким образом, техника разлома позволила трем исследователям свести любой ориентированный граф к комбинации двух особых случаев — DAG и плотных кластеров, — с каждым из которых было легко справиться.
Новый алгоритм поиска кратчайших путей многократно использует процедуру разлома, чтобы разбить граф на тесно связанные кластеры, соединенные DAG. Затем он разбивает эти кластеры дальше и дальше. В конце процесса кластеры на самом внутреннем уровне максимально тесно связаны. Одна из причин, по которой алгоритм настолько быстр, заключается в том, что не требуется много итераций, чтобы полностью разбить даже очень большой граф, точно так же, как не требуется много времени, чтобы сократить большое число до разумного размера, если вы многократно делите это пополам.
Таким образом, полностью разбивая граф, исследователи могли быстро найти кратчайшие пути через каждую часть графа. Для плотных кластеров на самом внутреннем уровне структуры вложенного графа это было легко — у них практически не осталось негатива. И исследователи уже знали, как найти кратчайшие пути на соединяющих их участках DAG.
Наконец, алгоритм добавляет ребра, удаленные в процессе разлома, и вычисляет их влияние на кратчайшие пути. Исследователи доказали, что их процесс случайного удаления ребер почти всегда требовал всего нескольких удалений для устранения «обратных» ребер — таких, которые превращали бы их DAG в граф с большими циклами. Это делало крайне маловероятным, что какой-либо кратчайший путь будет проходить через слишком много таких обратных сегментов, поэтому они смогли решить этот сложный последний шаг, объединив два метода из учебников 1950-х годов: алгоритм Дейкстры и первый алгоритм, разработанный для графов с отрицательным весом.
«Это чрезвычайно умная комбинация этих идей», — сказал Кханна. Алгоритм является первым для графов с отрицательным весом, который работает за «почти линейное» время — это означает, что его время выполнения почти пропорционально времени, необходимому только для подсчета всех ребер, что является самым быстрым из возможных.
А что насчет графиков с отрицательными циклами, которые исследователи решили игнорировать на старте? Внеся последние штрихи в свой алгоритм кратчайших путей, они показали, что он также может работать как быстрый алгоритм для точного определения отрицательных циклов. Практически ни один график не был вне его досягаемости.
Параллельные пути
Бернштейн представил результат команды на конференции «Основы компьютерных наук» 2022 года, где их рукопись, описывающая новый алгоритм, была признана одной из двух лучших статей. другая бумага также случилось описать новый алгоритм почти линейного времени для решения давней проблемы в теории графов.
Этот алгоритм, разработанный Пробстом Гутенбергом и пятью другими исследователями, решал более общую проблему, называемую потоком с минимальной стоимостью, в которой целью является оптимизация транспорта по множеству параллельных путей, и каждое ребро имеет максимальную пропускную способность, а также связанную с ней стоимость. . Задачи поиска кратчайших путей являются частным случаем потока с минимальной стоимостью, поэтому новый алгоритм потока с минимальной стоимостью можно также использовать для решения задачи поиска кратчайших путей с отрицательным весом за почти линейное время, хотя и с совершенно другим подходом.
Команда, работающая над потоком с минимальной стоимостью, разработала свой универсальный быстрый алгоритм, используя сложный синтез комбинаторных и непрерывных методов оптимизации, что делает его громоздким на практике, по крайней мере, в настоящее время. Комбинаторный алгоритм Бернштейна и его коллег, хотя и ограничен более конкретной задачей, достигает своего почти линейного времени выполнения без ущерба для простоты.
«Вот что удивительного в этой статье, — сказал Пробст Гутенберг. «Вы можете объяснить это студенту бакалавриата, а также можете реализовать это на своем компьютере».
В результате этот новый алгоритм возродил интерес к комбинаторным подходам к другим задачам теории графов. Остается выяснить, какие проблемы можно быстро решить с помощью чисто комбинаторных алгоритмов, а какие действительно требуют непрерывных методов, разработанных за последние 20 лет.
«Это философский вопрос, который я пытаюсь понять», — сказал Нанонгкай. «Эта задача о кратчайшем пути дает некоторую надежду».
- SEO-контент и PR-распределение. Получите усиление сегодня.
- Платоблокчейн. Интеллект метавселенной Web3. Расширение знаний. Доступ здесь.
- Источник: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/
- 20 лет
- 2021
- 2022
- a
- О нас
- По
- Учетная запись
- достигнутый
- через
- на самом деле
- ациклический
- приспосабливать
- Добавляет
- После
- против
- алгоритм
- алгоритмы
- Все
- уже
- всегда
- честолюбивый
- Древний
- и
- Другой
- кроме
- подхода
- подходы
- около
- связанный
- назад
- Баланс
- основанный
- , так как:
- становиться
- до
- начал
- верить
- Бернштейн
- ЛУЧШЕЕ
- между
- Beyond
- большой
- брать в долг
- Филиал
- Ломать
- брейки
- Сломанный
- исчисляет
- под названием
- Пропускная способность
- случаев
- случаев
- определенный
- СНГ
- Закрыть
- тесно
- Кластер
- сотрудничало
- коллеги
- сочетание
- комбинируя
- как
- расчеты
- компьютер
- Информатика
- концентрированный
- Конференция
- подключенный
- Соединительный
- Рассматривать
- Состоящий из
- (CIJ)
- Цена
- может
- Создайте
- Текущий
- В настоящее время
- Порез
- циклы
- DAG
- десятилетия
- решенный
- решения
- поставка
- описывать
- назначение
- определены
- развивать
- развитый
- DID
- Различия
- различный
- трудный
- направлять
- направление
- открытый
- расстояние
- не
- Dont
- вниз
- водитель
- Голландский
- каждый
- зарабатывать
- легче
- Простейший
- Edge
- эффекты
- ликвидировать
- устранен
- включен
- полностью
- по существу
- оценка
- Оценки
- Даже
- НИКОГДА
- все члены
- существующий
- существует
- эксперты
- Объяснять
- Исследование
- чрезвычайно
- содействовал
- вентилятор
- БЫСТРО
- быстрый
- Федеральный
- несколько
- окончательный
- в заключение
- Найдите
- обнаружение
- находит
- Во-первых,
- Впервые
- поток
- Потоки
- Фокус
- найденный
- Устои
- Freedom
- от
- полностью
- далее
- ГАЗ
- Общие
- общее назначение
- Germany
- получить
- данный
- дает
- Go
- цель
- график
- Графики
- Жадный
- гарантированный
- Гутенберг
- Половина
- горсть
- обрабатывать
- произошло
- Заголовок
- помощь
- высший
- надежды
- Как
- How To
- Однако
- HTML
- HTTPS
- идеи
- определения
- осуществлять
- in
- доход
- независимые
- individual
- информация
- вдохновленный
- пример
- Институт
- интерес
- Изобретенный
- включать в себя
- IT
- итерации
- присоединиться
- присоединение
- Основные
- Вид
- Знать
- известный
- большой
- больше
- уровень
- ЖИЗНЬЮ
- Ограниченный
- рамки
- связи
- локальным
- Длинное
- много времени
- давнишний
- дольше
- посмотреть
- сделанный
- сделать
- ДЕЛАЕТ
- Создание
- способ
- многих
- карта
- Совпадение
- математический
- Макс
- максимальный
- означает
- Между тем
- идти
- методы
- может быть
- Модерн
- деньги
- БОЛЕЕ
- движется
- перемещение
- почти
- отрицательный
- соседи
- Сети
- сеть
- Новые
- следующий
- узел
- узлы
- понятие
- номер
- номера
- смещение
- ONE
- открытый
- Операционный отдел
- оптимизация
- Оптимизировать
- оригинал
- порожденный
- Другое
- Другое
- в противном случае
- пакеты
- спаривание
- бумага & картон
- бумага
- Параллельные
- часть
- части
- Прохождение
- мимо
- путь
- Пенсильвания
- выбирать
- Платон
- Платон Интеллектуальные данные
- ПлатонДанные
- Точка
- пунктов
- положительный
- возможности,
- возможное
- практически
- практика
- представлены
- Проблема
- проблемам
- процесс
- Прибыль
- выгодную
- Прогресс
- Проект
- собственность
- доказанный
- приводит
- чисто
- Полагая
- Квантовый журнал
- вопрос
- быстро
- радикально
- случайный
- быстро
- достигать
- реальные
- реализованный
- причина
- разумный
- недавно
- уменьшить
- отражать
- районы
- относительно
- остались
- остатки
- повторный
- НЕОДНОКРАТНО
- представлять
- представленный
- представляет
- требовать
- обязательный
- исследованиям
- исследователи
- ответственный
- ограниченный
- результат
- в результате
- Предложение
- Дорога
- дорога
- Run
- Бег
- Rutgers University
- пожертвовав
- Сказал
- то же
- Наука
- Ученый
- Ученые
- поиск
- разделах
- сегмент
- сегментами
- смысл
- Серии
- Стабильный
- несколько
- Короткое
- аналогичный
- просто
- простота
- с
- одинарной
- Размер
- небольшой
- So
- РЕШАТЬ
- Решение
- некоторые
- Кто-то
- удалось
- где-то
- сложный
- Источник
- Источники
- особый
- конкретный
- скорость
- SPELL
- раскол
- стандарт
- Начало
- и политические лидеры
- Начало
- Шаг
- По-прежнему
- История
- Стратегия
- поток
- улица
- Структура
- "Студент"
- такие
- лето
- швейцарский
- взять
- принимает
- с
- команда
- снижения вреда
- Технологии
- говорит
- учебник
- Ассоциация
- График
- Источник
- их
- вещи
- три
- Через
- время
- в
- вместе
- слишком
- тема
- трогательный
- перевозки
- Путешествие
- беда
- правда
- ОЧЕРЕДЬ
- Оказалось
- лежащий в основе
- понимать
- Университет
- обновление
- использование
- отпуск
- фактически
- стремятся
- Вода
- WebP
- вес
- Что
- будь то
- который
- КТО
- в
- без
- Работа
- работает
- работает
- бы
- лет
- Ты
- ВАШЕ
- зефирнет
- Цюрих