[Перевод] Учёные нашли оптимальный способ обхода графа
Алгоритм Дейкстры долгое время считался самым эффективным способом обхода графа. Теперь исследователи доказали, что он «универсально оптимален».
Если вы долгое время ездите по одному и тому же маршруту, вы, вероятно, считаете его лучшим. Но «лучший» — это относительное понятие. Возможно, однажды произойдёт авария или дорога будет перекрыта, и ваш самый быстрый маршрут станет самым медленным.
Подобные сценарии также являются вызовом для исследователей, которые разрабатывают алгоритмы, пошаговые процедуры, которые компьютеры используют для решения проблем. Множество различных алгоритмов могут решить любую заданную проблему, и вопрос, какой из них лучше, может быть удручающе неоднозначным.
Представьте себе алгоритм, который разработан для поиска самого быстрого маршрута между двумя точками. Существует множество возможных способов разработать такой алгоритм так, чтобы он не давал сбоев. Успешный алгоритм всегда будет возвращать самый быстрый маршрут, и неважно, используете ли вы его в Лондоне или Лос-Анджелесе, и час пик это или середина ночи.
Но не все эти алгоритмы одинаковы. Время, необходимое каждому из них для нахождения правильного ответа, будет зависеть от того, где и когда он используется, и случаи, которые сложны для одного алгоритма, могут быть простыми для другого. В идеале вам нужен алгоритм, который всегда работает быстрее других.
Для большинства задач просто невозможно найти такого «единорога». Но новое доказательство показывает, что для типичной задачи поиска пути один алгоритм близок к идеалу: при наихудших схемах движения, это лучший подход для каждой возможной сети улиц. Более того, алгоритму почти 70 лет, и он является основным элементом программы бакалавриата по информатике. Новая работа была представлена к награде за лучшую статью на Симпозиуме по основам информатики в октябре 2024 года.
«Это потрясающе», — сказал Тим Рафгарден, специалист по информатике из Колумбийского университета. «Я не могу представить себе более убедительную исследовательскую работу о проблеме, которую мы преподаём студентам на курсах алгоритмов».
Кучи и границы
История этого знакового алгоритма поиска пути началась необычно. В 1956 году 26-летний голландский учёный Эдсгер Дейкстра хотел написать программу, которая продемонстрировала бы возможности совершенно нового компьютера под названием ARMAC.
Во время прогулки за покупками со своей невестой в Амстердаме он остановился в кафе, чтобы сделать перерыв. Именно тогда ему пришла в голову идея алгоритма, который теперь носит его имя. У него не было под рукой письменных принадлежностей, поэтому в течение 20 минут он прорабатывал детали в голове.
Эдсгер Дейкстра разработал классический алгоритм для быстрого поиска кратчайших путей в сети. Снимок сделан в 2002 году.
В интервью в конце своей жизни Дейкстра объяснил непреходящую привлекательность своего алгоритма отчасти его необычной историей происхождения. «Без карандаша и бумаги вы вынуждены избегать всех возможных сложностей», — сказал он.
Алгоритм Дейкстры не просто сообщает вам самый быстрый маршрут до одного пункта назначения. Вместо этого он даёт вам упорядоченный список времени в пути от вашего текущего местоположения до любой другой точки, которую вы, возможно, захотите посетить. Это решение того, что исследователи называют проблемой кратчайших путей из одного источника. Алгоритм работает в абстрактной дорожной карте, называемой графом: сетью взаимосвязанных точек (называемых вершинами), в которой связи между вершинами помечены числами (называемыми весами). Эти веса могут представлять время, необходимое для прохождения каждой дороги в сети, и они могут меняться в зависимости от схем движения. Чем больше вес, тем больше времени требуется для прохождения этого пути.
Чтобы получить представление об алгоритме Дейкстры, представьте, что вы путешествуете по графу, записывая время в пути от начальной точки до каждой новой вершины на листе бумаги. Всякий раз, когда у вас есть выбор, в каком направлении ехать дальше, направляйтесь к ближайшей вершине, которую вы ещё не посетили. Если вы обнаружите более быстрый путь к какой-либо вершине, запишите новое время и вычеркните старое. Когда вы будете уверены, что нашли самый быстрый путь, перенесите время в пути из своих заметок в отдельный, более презентабельный список.
«Это отличный алгоритм», — сказал Эрик Демейн, специалист по информатике из Массачусетского технологического института. «Он очень быстрый, простой и лёгкий в реализации».
Чтобы реализовать эту процедуру на практике, вам нужно будет выбрать систему для организации ваших заметок — структуру данных, на жаргоне компьютерных наук. Это может показаться незначительной технической деталью, но время, потраченное на поиск в ваших заметках, когда вам нужно отредактировать или удалить запись, может оказать большое влияние на общее время выполнения алгоритма.
В статье Дейкстры использовалась простая структура данных, которая оставляла место для улучшения. В последующие десятилетия исследователи разработали лучшие структуры, названные «кучами», в которых некоторые элементы найти легче, чем другие. Они используют тот факт, что алгоритму Дейкстры нужно удалить только запись для ближайшей оставшейся вершины. «Куча — это, по сути, структура данных, которая позволяет вам сделать это очень быстро», — сказал Вацлав Рожон, исследователь из Института компьютерных наук, искусственного интеллекта и технологий (INSAIT) в Софии, Болгария.
В 1984 году двое учёных разработали конструкцию кучи, которая позволила алгоритму Дейкстры достичь теоретического предела, или «нижней границы», времени, необходимого для решения задачи поиска кратчайших путей из одного источника. В одном конкретном смысле эта версия алгоритма Дейкстры является наилучшей из возможных. Это было последнее слово в стандартной версии задачи на протяжении почти 40 лет. Всё изменилось, когда несколько исследователей более внимательно изучили, что значит быть «лучшим».
Лучшее поведение
Исследователи обычно сравнивают алгоритмы, изучая, как они справляются с наихудшими сценариями. Представьте себе самую запутанную уличную сеть в мире, а затем добавьте несколько особенно проблемных схем движения. Если вы настаиваете на поиске самых быстрых маршрутов в этих экстремальных условиях, версия алгоритма Дейкстры 1984 года, очевидно, лучшая.
Но, надеюсь, в вашем городе не самая худшая в мире уличная сеть. И поэтому вы можете спросить: есть ли алгоритм, который был бы лучшим на любой дорожной сети? Первый шаг к ответу на этот вопрос — сделать консервативное предположение, что каждая сеть имеет наихудшие схемы движения. Затем вы хотите, чтобы ваш алгоритм находил самые быстрые пути через любую возможную схему графа, предполагая наихудшие возможные веса. Исследователи называют это условие «универсальной оптимальностью». Если бы у вас был универсально оптимальный алгоритм, который решает более простую задачу: добраться из одной точки на графе в другую, он мог бы помочь вам обойти пробки в час пик в любом городе мира.
«Это звучит слишком хорошо, чтобы быть правдой», — сказал Бернхард Хойплер, учёный, работающий в INSAIT и Швейцарском федеральном технологическом институте Цюриха (ETH Zurich).
Хойплер был очарован возможностями универсальной оптимальности, когда писал заявку на грант в середине 2010-х годов. Многие исследователи считают эту часть работы утомительной, но Хойплер увидел в ней возможность. «Это позволяет вам отбросить свой скептицизм и просто мечтать по-крупному», — сказал он.
Эти мечты воплотились в жизнь в 2021 году, когда Хойплер и два аспиранта доказали, что можно построить универсально оптимальные алгоритмы для нескольких важных задач на графах. Он не подумал выяснить, достижимо ли то же самое условие для классической задачи поиска кратчайших путей из одного источника. Эта проблема должна была подождать, пока другой аспирант не осмелится мечтать по-крупному.
Кратчайший путь к победе
В начале 2023 года Рожон был на заключительном этапе своей аспирантской программы в ETH Zurich. Он только что закончил работу над статьёй о выходе за рамки анализа наихудшего случая в другом контексте и обдумывал новые идеи для реализации со своим соавтором Якубом Тетеком, аспирантом Копенгагенского университета. Рожон предложил ему попытаться разработать универсально оптимальный алгоритм для задачи поиска кратчайших путей из одного источника.
«Я сказал: «Нет, но это невозможно; это просто невозможно сделать», — вспоминает Тетек. Но Рожон убедил его попробовать. Весной команда выросла до трёх человек с добавлением Ричарда Хладика, аспиранта ETH Zurich, с которым Рожон и Тетек познакомились, когда все трое были старшеклассниками в Чешской Республике.
Трио экспериментировало со многими различными аспектами алгоритма Дейкстры и кучей, которую он использовал, и им удалось найти универсально оптимальный вариант. Но полученный алгоритм был сложным, и они не смогли точно определить, какие условия были необходимы для универсальной оптимальности. В области, которая живёт на всесторонних и строгих доказательствах, этого было недостаточно.
Три студента перешли от математических сетей к социальным. Рожон начал обсуждать проблему с Хойплером, когда оба навещали коллег в Нью-Йорке. Оттуда Хойплер полетел в Панаму на каникулы, но он не был готов отложить проблему в сторону.
«Это был мой отпуск», — сказал он. «Но несмотря на это, размышления не прекращались».
Слева направо: Бернхард Хёплер, Вацлав Рожон (вверху), Якуб Тетек (внизу), Роберт Тарьян и Рихард Хладик доказали, что версия алгоритма Дейкстры — лучший подход для любой схемы сети.
Во время звонка в Zoom через несколько дней после начала поездки Хойплера команда из четырёх человек остановилась на новом подходе. Они решили сосредоточиться в основном на выборе структуры данных. Вскоре они начали подозревать, что этого будет достаточно — они могли оставить остальную часть алгоритма Дейкстры нетронутой. В течение месяца они это доказали.
Ключевым ингредиентом оказалось особое свойство некоторых структур данных, которое позволяет им быстро получать доступ к недавно добавленным элементам. Кучи с этим свойством были впервые построены более 20 лет назад, но за все последующие годы никто не использовал его в полной мере. Четверо исследователей доказали, что им нужно было только построить структуру данных с этим новым свойством и всеми другими функциями кучи 1984 года. Теперь им оставалось только спроектировать её.
Последним, кто присоединился к команде, был Роберт Тарьян, учёный из Принстонского университета, который был одним из изобретателей этой особой кучи 1984 года. Тарьян получил премию Тьюринга — высшую награду в этой области, а также был наставником Хойплера в конце 2000-х. Когда Тарьян посетил Цюрих в мае, Хойплер пригласил его на фондю — который он отлично готовит — и упомянул новый проект по поиску кратчайших путей. Тарьян сразу же приступил к работе.
Пятеро исследователей принялись за разработку кучи со всеми необходимыми им свойствами. Они начали с громоздкого дизайна и совершенствовали его понемногу, пока не остались довольны. «Каждый раз, когда мы смотрели на него, нам удавалось немного его упростить», — сказал Рожон. «Я был на самом деле удивлён, насколько простым он оказался в итоге».
Некоторые варианты алгоритма Дейкстры нашли реальное применение в программном обеспечении, таком как Google Maps. Новый результат, вероятно, не будет иметь таких практических приложений, для которых есть много примеров за пределами теоретических гарантий оптимальности. Но он может изменить то, как исследователи изучают оптимальность, побуждая их смотреть дальше обычного анализа наихудших случаев. Часто алгоритмы достигают более сильных гарантий только за счёт дополнительной сложности. Новый результат показывает, что простые алгоритмы, имеющие сильные гарантии, могут быть более распространены, чем исследователи считали ранее — команда уже выявила два других примера.
«Общая концепция очень убедительна», — сказал Тарьян. «Остаётся посмотреть, насколько далеко это может зайти».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
