Исследователи разработали схему закраски рёбер графа, которая практически максимально быстра. Комментарий Сохранить статью Прочитать позже
Введение
Вот пугающий сценарий: вас назначили ответственным за управление воздушным движением в аэропорту Ньюарк, недалеко от Нью-Йорка. Вам нужно убедиться, что каждый самолёт может прорулить между взлётно-посадочной полосой и выходом на посадку, не задев другие самолёты.
Давайте применим силу математики к вашей задаче. Для начала создайте большую абстрактную карту вашего аэропорта. Отметьте точки для каждой взлётно-посадочной полосы, рулёжной дорожки и выхода на посадку. Затем для каждого самолёта проведите линию, соединяющую эти точки: Если самолёту нужно пролететь от взлётно-посадочной полосы 4L по рулёжной дорожке K до выхода на посадку C80, проведите линию, соединяющую точки для взлётно-посадочной полосы 4L, рулёжной дорожки K и выхода на посадку C80.
Теперь самое главное: избежать столкновений. Вы заметите, что в каждое физическое место входит и выходит множество самолётов — множество линий, соединённых с каждой точкой на карте, которую исследователи называют графом. Чтобы гарантировать, что никакие два самолёта не находятся в одном и том же месте в одно и то же время, можно раскрасить каждую из линий и потребовать, чтобы для каждой точки не было двух линий, соединённых с ней, одного цвета. Цвета представляют собой время; требуя, чтобы все цвета, сходящиеся в одной точке, были разными, вы предотвращаете нахождение самолётов в одном и том же месте в одно и то же время.
Теперь вам остаётся только заполнить цвета. В случае аэропорта это, возможно, можно сделать вручную, даже для такого крупного аэропорта, как Ньюарк. Но исследователи обычно анализируют графы с миллиардами и более соединений. Поэтому они разработали алгоритмы, которые назначают им цвета.
Однако эти алгоритмы медленные и «застряли более или менее на одном и том же уровне за последние 40 лет», — говорит Сепер Ассади, специалист по информатике из Университета Ватерлоо в Канаде.
Затем, в 2024 году, в течение нескольких дней две разные группы исследователей разработали новые алгоритмы, значительно превосходящие по скорости старый стандарт. В докладе, который будет представлен в июне на Симпозиуме по теории вычислений 2025 года, этот подход идёт ещё дальше. В нём описывается почти оптимальный алгоритм — практически максимально быстрый. Удивительно, но этот новый алгоритм вообще не зависит от количества точек на графике, а зависит только от количества линий. Теперь не имеет значения размер вашего аэропорта, важно лишь количество маршрутов, по которым движутся самолёты.
По словам Антона Бернштейна, математика из Калифорнийского университета в Лос-Анджелесе, эта новая работа «почти полностью решила проблему». Это «важное достижение, которое мало кто мог предсказать ещё пару лет назад».
Жизнь на грани
В 1964 году математик Вадим Визинг доказал шокирующий результат: каким бы большим ни был граф, легко рассчитать, сколько цветов потребуется для его раскраски. Просто найдите максимальное количество линий (или рёбер), соединённых с одной точкой (или вершиной), и прибавьте 1.
Однако проблема заполнения этих цветов оказалась совсем другой. Визинг придумал свой алгоритм раскраски, но он был медленным. Он начал с того, что посчитал время, необходимое для раскраски всего одного оставшегося ребра полностью раскрашенного графа. Раскраска этого ребра могла означать изменение цвета смежных с ним ребер, и так далее. Визинг подсчитал, что раскраска одного ребра может занять — максимум — время, пропорциональное общему количеству вершин, которое он обозначил как n. Если всего имеется m ребер, алгоритм Визинга даёт время раскраски всего графа, пропорциональное произведению m на n.
Это значение сохранялось около 20 лет, пока работы 1980-х годов не позволили снизить время раскрашивания рёбер. Новое значение было пропорционально m, умноженному на квадратный корень из n. Однако методы, лежащие в основе этих улучшений, не привели к дальнейшему прогрессу. Другие исследователи не смогли их улучшить, и прогресс застопорился.
Затем, в мае 2024 года, Ассади опубликовал статью на сайте научных препринтов arxiv.org, в которой показал, как раскрасить граф за время порядка n² — фактор, зависящий только от количества вершин. Для некоторых графов, где количество вершин значительно меньше количества рёбер, это значительное улучшение.
Примерно в то же время команда, не связанная с Ассади, опубликовала свой результат, сокративший время раскраски рёбер до порядка m, умноженного на кубический корень из n. Они добились этого, найдя немного более быстрый способ раскраски одного ребра. В последующей работе команда внесла дальнейшее усовершенствование, в результате чего общее время выполнения стало пропорционально m, умноженному на корень четвёртой степени из n.
Летом группа начала сотрудничать с Ассади и новым членом команды, Сохеилом Бехнежадом из Северо-Восточного университета. Но вместо того, чтобы стремиться к постепенным улучшениям, они стремились к более фундаментальному результату. «Как только мы нашли способ обойти этот [старый результат], — сказал Ассади, — мы не видели никаких фундаментальных препятствий впереди».
Новообразованная группа решила стремиться к конечной цели: теоретически минимальному времени. Самое быстрое время, за которое можно пройти весь граф и просто посмотреть, как он выглядит — отметить, что это ребро красное, следующее — синее и так далее, — это всего лишь m, количество рёбер. Поскольку красить рёбра невозможно быстрее, чем считывать их, это «линейное время» m также является кратчайшим возможным временем раскраски.
Но для достижения такой скорости они не могли полагаться на те же приёмы, что и в предыдущих работах. «Мы понимали, что предложенные нами методы позволяют добиться некоторого улучшения, но ни один из них не обладал достаточной мощностью, чтобы сократить время выполнения алгоритма до почти линейного», — сказал Мартин Коста, докторант Уорикского университета и соавтор нескольких работ по раскраске рёбер, включая прошлогодние достижения. Коста добавил, что, если они хотели хоть как-то достичь этой цели, «нам пришлось использовать совершенно другой подход».
Грунтовка под покраску
Команда обнаружила, что, начиная с работ 2024 года и вплоть до самого Визинга, все стратегии страдали от одного и того же узкого места. Напомним, что Визинг исходил из наихудшего сценария: раскрашивать последнее возможное ребро графа, а затем менять цвета всех остальных соединённых с ним рёбер. «Предыдущая работа была сосредоточена на том, чтобы попытаться раскрасить это последнее ребро быстрее», — сказал Ассади. «Поэтому мы использовали другой способ». Вместо того, чтобы пытаться раскрасить одно ребро быстрее, они хотели посмотреть, насколько быстро можно раскрасить несколько рёбер практически одновременно.
Сохейл Бехнежад вместе с Костой, Ассади и другими разработали алгоритм, который раскрашивает граф практически с максимально возможной скоростью.
Для этого команда позаимствовала концепцию из неожиданного источника: ремонта дома. Если вы собираетесь перекрасить стены, вы сначала наносите слой грунтовки, чтобы вернуть им нейтральный цвет. Таким же образом исследователи попытались «загрунтовать» граф — перевести его в новое состояние, которое было бы легче раскрашивать. Для этого они использовали методы рандомизации, по сути полагаясь на результаты многочисленных подбрасываний монеты, чтобы раскрасить большую часть графа, оставив определенные края стратегически неокрашенными. После грунтовки эти последние области можно было раскрасить просто и почти одновременно. Новый быстрый алгоритм команды может раскрашивать граф «почти линейно» — порядка m, умноженных на логарифм m.
«Это прорыв, потрясающий результат», — сказал Роберт Тарьян, специалист по информатике из Принстонского университета и лауреат премии Тьюринга, считающейся высшей наградой в этой области. Стратегия команды по подготовке графа оказалась новаторской. «Эта одна новая идея буквально изменила всё», — сказал Тарьян.
Дэвид Вайц, специалист по информатике из Техниона в Хайфе, Израиль, считает результат «вдохновляющим» — он стал кульминацией десятилетий исследований, начиная с 1960-х годов.
За пределами почти совершенства
Хотя теоретики, возможно, и празднуют, пока неясно, приведёт ли этот результат к реальному ускорению. Хотя теоретиков обычно не интересуют постоянные множители, «на практике они имеют значение», отметил Бехнежад. Достигнутое ими время выполнения пропорционально m log m или, что то же самое, константе, умноженной на m log m. «В этом алгоритме эта константа, похоже, очень мала», — сказал он. «Это один из признаков того, что этот алгоритм может быть практичным».
Тем временем группа размышляет, как ещё больше улучшить свой результат. Исследователи хотели бы проверить, смогут ли они достичь почти линейного времени без какой-либо случайности. «Это теоретически интересно, и было бы также приятно знать, что ваш алгоритм всегда будет работать точно за это время, и нет никаких шансов, что он когда-либо будет работать медленно», — сказал Коста.
Кроме того, команда хотела бы проверить, можно ли удалить этот дополнительный логарифмический член из времени выполнения, чтобы сделать результат не просто почти линейным, а абсолютно линейным. «В этом и заключается разница между тем, что мы получаем, и лучшим, на что можно надеяться, — сказал Ассади, — но существует очень мало задач на графы, где мы действительно можем удалить этот член».
Для Тарьяна, безусловно, было бы интересно исключить рандомизацию и логарифмический член, «но это и то, и другое — огромные проблемы», — сказал он. «Я думаю, этот результат будет соответствовать последнему слову техники в обозримом будущем».
Источник: www.quantamagazine.org
