Два учёных-компьютерщика нашли в очень неожиданном месте идею, которая как раз подходила им для того, чтобы совершить прорыв в теории графов.
В октябре 2019 года Джейкоб Холм И Ева Ротенберг листали работу, опубликованную несколькими месяцами ранее, — и вдруг поняли, что наткнулись на что-то серьезное.
На протяжении десятилетий ученые-компьютерщики пытались разработать быстрый алгоритм, позволяющий определить, можно ли добавить ребра в данный граф так, чтобы он оставался «плоским», то есть без пересечения его ребер.
Однако никто не смог улучшить алгоритм, опубликованный более 20 лет назад. Холм и Ротенберг были удивлены, обнаружив, что в их работа Есть идея, которая могла бы существенно улучшить этот алгоритм.
Она «решила одно из главных препятствий на пути к созданию настоящего алгоритма», — сказал Холм, ученый-компьютерщик из Копенгагенского университета.
«Возможно, мы полностью решили эту проблему».
Пара поспешила приступить к работе.
Они представили его в июне на Симпозиум по теории вычислений , проведенный Ассоциацией вычислительной техники, где подробно описали метод проверки графа на планарность, который экспоненциально превосходит предыдущий вариант. «Новый алгоритм поистине мастерский», — сказал Джузеппе Итальяно , учёный-компьютерщик из Университета Луи, соавтор работает с 1996 года , где сейчас описан второй по скорости алгоритм.
«Когда я участвовал в написании этой статьи, я не думал, что такое может произойти».
Графы — это множества вершин, соединенных ребрами.
Их можно использовать для маркировки всего: от социальных сетей до дорожных сетей и электрических проводников на плате.
Если в последнем случае граф не плоский, то два проводника пересекутся, что приведет к короткому замыканию.
Еще в 1913 году планарные графы появились в комплексной «полезности».
задача про три дома , опубликованное в журнале The Strand Magazine. Издание попросило читателей проложить коммуникации для трех домов, соединив каждый из них тремя энергоносителями - водой, газом и электричеством - чтобы коммуникации не пересекались друг с другом.
Не нужно много времени, чтобы понять, что эта проблема невозможна.
Однако в случаях с более сложными графами не всегда очевидно, являются ли они планарными.
Еще труднее сказать, останется ли сложный граф плоским, когда вы начнете добавлять к нему ребра, как это происходит при прокладке новых дорог.
Ученые-компьютерщики уже давно ищут алгоритм, который сможет быстро определить, можно ли внести желаемое изменение, чтобы граф оставался плоским, без перебора каждой части графа, когда изменяется лишь небольшая его часть.
Алгоритм 1996 года требовал для этого ряда шагов, примерно пропорциональных квадратному корню из числа вершин в графе.
«Это намного лучше, чем каждый раз тестировать все с нуля, но это не идеально», — сказал Холм.
Новый алгоритм проверяет планарность за количество шагов, пропорциональное кубу логарифма количества вершин в графе — улучшение экспоненциальное.
Холм и Ротенберг из Технического университета Дании добились такого ускорения, воспользовавшись особым свойством плоских графов, которое они открыли в прошлом году.
Чтобы понять их метод, сначала нужно заметить, что тот же плоский граф ты можешь рисовать по-разному .
Все соединения этих вариантов остаются прежними, но края могут располагаться относительно друг друга по-разному.
Например, рисунок А можно изменить на рисунок Б, перевернув треугольник, составляющий вершины 1, 2 и 3, относительно ребра, соединяющего вершины 2 и 3. Верхняя часть рисунка В также может отражаться относительно вершин 4 и 5. , в результате чего получается рисунок C. Рисунки выглядят по-разному, но представляют собой один и тот же граф.
Теперь представьте, что вы хотите вставить новое ребро, соединяющее две вершины планарного графа, скажем, вершины 1 и 6. Для этого вы выполняете последовательность переворотов.
Из исходного положения слева за два оборота можно переместить вершину 1 в место, где ее можно соединить с вершиной 6, не пересекая при этом другие ребра.
В статье 2019 года Холм и Ротенберг обнаружили, что некоторые шаблоны имеют больше преимуществ для вставки ребер, чем другие.
Эти «хорошие» конструкции требуют всего лишь нескольких поворотов, чтобы добавить новую грань, не нарушая при этом плоскостности.
В октябре они с опозданием поняли, что переворот, который приближает вас к позиции, в которой вы можете добавить новое ребро, также приближает график к одному из действительных планов, которые они уже идентифицировали.
Показав, что последовательность переворотов неизбежно приближает граф к предпочтительным шаблонам, вы можете создать новый алгоритм, который ограничивает количество переворотов, которые вам могут понадобиться, чтобы найти способ добавить ребро (если это вообще возможно).
«Мы очень быстро поняли, что с помощью этого нового анализа проблему можно решить.
Алгоритм чрезвычайно прост по своей концепции», — сказал Холм.
Ева Ротенберг и Якоб Хольм
Новый алгоритм выполняет по одному перевороту в поисках решения.
В результате происходит одно из двух: либо алгоритм находит способ вставить необходимое ребро, либо следующий оборот отменяет предыдущий — после чего алгоритм приходит к выводу, что добавить новое ребро невозможно.
«Мы называем этот алгоритм ленивым-жадным», — пояснил Ротенберг.
«Он вносит только изменения, необходимые для размещения нового ребра».
Их новый метод близок к производительности наилучшего алгоритма для аналогичных задач, но не соответствует ему.
Новый алгоритм также должен пройти слишком много шагов, чтобы быть полезным в большинстве реальных приложений — графики обычно достаточно просты, чтобы их можно было протестировать методом грубой силы.
Но для Холма и Ротенберга скорость алгоритма не так важна, как идеи, которые его ускоряют. «Это понимание имеет немедленные последствия», — сказал Ротенберг.
Итальяно полагает, что в конечном итоге оно найдет практическое применение.
«Рано или поздно это обязательно повлияет на вещи, выходящие за рамки информатики и математики», — сказал он.
Никто не знает, когда могут появиться еще более быстрые алгоритмы.
Это может потребовать совершенно нового прорыва, или секретный ингредиент может уже где-то существовать, ожидая своего часа в груде старых исследований.
Теги: #Популярная наука #математика #графы #теория графов #плоские графы
-
Гугл: Блокировка Рекламы
19 Oct, 24 -
Офис Мониторинга Кампании
19 Oct, 24 -
Тип Звука № 45
19 Oct, 24 -
Сайт О Специальных Гаджетах Для Гиков
19 Oct, 24
