Исторические алгоритмы помогают разблокировать прорыв в проблеме нахождения кратчайшего пути

Historical algorithms aid in unlocking a breakthrough in the shortest path problem.

.fav_bar { float:left; border:1px solid #a7b1b5; margin-top:10px; margin-bottom:20px; } .fav_bar span.fav_bar-label { text-align:center; padding:8px 0px 0px 0px; float:left; margin-left:-1px; border-right:1px dotted #a7b1b5; border-left:1px solid #a7b1b5; display:block; width:69px; height:24px; color:#6e7476; font-weight:bold; font-size:12px; text-transform:uppercase; font-family:Arial, Helvetica, sans-serif; } .fav_bar a, #plus-one { float:left; border-right:1px dotted #a7b1b5; display:block; width:36px; height:32px; text-indent:-9999px; } .fav_bar a.fav_de { background: url(../images/icons/de.gif) no-repeat 0 0 #fff } .fav_bar a.fav_de:hover { background: url(../images/icons/de.gif) no-repeat 0 0 #e6e9ea } .fav_bar a.fav_acm_digital { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_acm_digital:hover { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_pdf { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_pdf:hover { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_more .at-icon-wrapper{ height: 33px !important ; width: 35px !important; padding: 0 !important; border-right: none !important; } .a2a_kit { line-height: 24px !important; width: unset !important; height: unset !important; padding: 0 !important; border-right: unset !important; border-left: unset !important; } .fav_bar .a2a_kit a .a2a_svg { margin-left: 7px; margin-top: 4px; padding: unset !important; }

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

Недавний прорыв в комбинаторных техниках показал, как можно возродить эти ранние алгоритмы.

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

• Ученые-компьютерщики Университета Калифорнии в Сан-Диего борются с ежегодным отходом 1,5 миллиарда выброшенных смартфонов
• Парадокс силы искусственного интеллекта
• Этот стартап разработал умный способ повторного использования отходящего тепла от облачных вычислений

Проблемы начинаются, когда вы сталкиваетесь с аналогичной сетью, где пути могут иметь отрицательные веса. “Когда вы имеете дело с ситуацией, когда веса ребер соответствуют стоимости, отрицательные веса являются естественными”, говорит Аарон Бернштейн, доцент кафедры компьютерных наук в Рутгерском университете, Нью-Брансуик, Нью-Джерси.

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

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

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

Хотя компьютерные ученые пытались найти более эффективные решения проблемы, используя аналогичные комбинаторные методы, как в этих долговечных алгоритмах, им не удалось существенно сократить вычислительный разрыв между ними. В течение последних нескольких десятилетий больший прогресс был достигнут путем представления графа в виде коэффициентов матрицы и использования инструментов линейной алгебры. Такие методы доказали свою эффективность для широкого спектра задач, связанных с путями, не только для определения кратчайшего пути, но и для приложений, таких как максимизация потока через сеть труб или транспортных маршрутов, как это было продемонстрировано в докладе, представленном на Symposium on Foundations of Computer Science (FOCS) в прошлом году.

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

Недостатком недавно разработанных методов, основанных на оптимизации, является то, что они сложнее в реализации и понимании, чем традиционные комбинаторные алгоритмы. “Этот тип подхода часто использует множество динамических алгоритмов, которые обычно сложны. Они включают множество движущихся частей, которые нужно объединить вместе”, говорит Данупон Нанонгкай, директор и научный сотрудник Института информатики имени Макса Планка в городе Заарбрюккен, Германия.

Алгоритм Беллмана-Форда правильно обрабатывает отрицательные связи по весу, но уступает по эффективности технике Дейкстры.

Бернштейн, Нанонгкай и Кристиан Вульф-Нильсен, доцент кафедры информатики Копенгагенского университета, хотели узнать, смогут ли они найти эффективное комбинаторное решение для проблемы кратчайшего пути от одного источника с отрицательными весами.

Команда сначала обратилась к статье начала 1990-х годов Андрея Голдберга и его коллег, которая сократила сложность до квадратного корня из произведения количества вершин на количество узлов, пытаясь масштабировать значения весов, чтобы они стали положительными и позволить находить кратчайший путь с помощью подхода Дейкстры. “Изначально целью было просто немного улучшить результат Голдберга, но в конце концов оказалось, что, когда все было на своем месте, мы смогли пройти до конца”, говорит Нанонгкай.

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

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

Команда обнаружила, что было возможно разделить исходный граф на кластеры подграфов с маленьким диаметром и затем постепенно изменять веса с помощью серии функций цены, чтобы создать перестроенный граф, который можно было обработать практически полностью с использованием алгоритма Дейкстры. Это включало случайное удаление путей с отрицательными весами, которые позволяли преобразовать исходный граф в ориентированный ациклический граф: граф, в котором есть только прямые пути и нет петель, соединяющих сильно связанные кластеры друг с другом. Эта форма была выбрана, потому что она открыла возможность использования наиболее быстрого алгоритма. В последующей фазе вводятся пропущенные пути с отрицательными весами. Малое количество этих путей может быть обработано с помощью алгоритма Беллмана-Форда с сравнительно небольшим влиянием на время выполнения.

Хотя форма разложения с маленьким диаметром, созданная для ориентированных графов, оказалась фундаментальной для решения, Бернштейн говорит, что изначально это не было очевидным, поскольку традиционное разложение было разработано для неориентированных графов. “Когда мы начали рассматривать это, было неясно, что означает разложение с маленьким диаметром в этом контексте, и нам не пришло в голову, что это может быть соответствующая идея. Мы начали работать с другого направления и обнаружили, что имеем дело с графами, связанными с свойством маленького диаметра”, – говорит он.

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

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

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

Вульфф-Нильсен отмечает: “Это прогрессивное улучшение достигается путем нескольких изменений ребер с использованием функций цены. Так что это не так, будто мы просто находим одну цену.”

Результатом был алгоритм с почти линейной производительностью, и с немного лучшей производительностью по сравнению с техникой оптимизации максимального потока, представленной Ченом на том же мероприятии FOCS в прошлом году. Оба получили премию за лучшую научную статью на симпозиуме, и некоторые учителя с тех пор включили комбинаторный алгоритм и коллег в свои занятия из-за его относительной простоты.

Хотя основной алгоритм почти линейный, у него есть несколько элементов, которые имеют логарифмическую зависимость от количества вершин в графе, каждый из которых представляет возможность для улучшения. Карл Брингманн и Алехандро Кассис из Университета Заарланда сотрудничали с Ником Фишером из Института науки Вейцмана в Израиле и смогли оптимизировать шесть из восьми логарифмических факторов в статье, опубликованной в апреле. Некоторые из них они считали простыми, такими как изменение порядка представления элементов в основном алгоритме Дейкстры, но другие были “более сложными”.

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

Такие подходы могут оказаться таким же полезными для ориентированных графов, как низкодиаметральная декомпозиция для работы с неориентированными графами. “Я думаю, что люди были взволнованы тем, что низкодиаметральная декомпозиция может быть использована таким образом. Люди говорили с нами о возможности использования этого для других проблем с ориентированными графами”, утверждает Бернштейн.

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

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

Дополнительное чтение

Бернштейн, А., Нанонгкай, Д. и Вульфф-Нильсен, С. Одноисточниковые кратчайшие пути с отрицательными весами за почти линейное время. Материалы 63-го ежегодного симпозиума IEEE по основам науки о вычислительной технике (2022), 600–611

Чен, Л., Кинг, Р., Лиу, Я.П., Пенг, Р., Пробст Гутенберг, М. и Сачдева, С. Максимальный поток и минимально-стоимостный поток за почти линейное время. Материалы 63-го ежегодного симпозиума IEEE по основам науки о вычислительной технике (2022), 612–623

Брингманн, К., Кассис, А. и Фишер, Н. Одноисточниковые кратчайшие пути с отрицательными весами за почти линейное время: теперь быстрее! ArXiv 2304.05279 (2023)

Линиал, Н. и Сакс, М. Декомпозиции графов с низким диаметром. Combinatorica 13 (4) (1993), 441–454

Вернуться в начало

Автор

Крис Эдвардс – писатель из Суррея, Великобритания, который освещает темы электроники, информационных технологий и синтетической биологии.

©2023 ACM 0001-0782/23/8

Разрешается создавать цифровые или печатные копии части или всего данного произведения для личного или учебного использования без оплаты, при условии, что копии не создаются или не распространяются с целью извлечения прибыли или коммерческой выгоды и что копии содержат этот уведомление и полное цитирование на первой странице. Авторское право на компоненты данного произведения, принадлежащие другим лицам, кроме ACM, должно быть уважено. Разрешается делать аннотации с указанием авторства. Для воспроизведения, публикации, размещения на серверах или распространения в списках требуется предварительное специальное разрешение и/или оплата. Запрос на разрешение на публикацию отправляйте на permissions@acm.org или факс (212) 869-0481.

Цифровая библиотека публикуется Ассоциацией вычислительной техники. Авторское право © 2023 ACM, Inc.