Торуп и Томассен представили на FOCS алгоритм раскраски карт в четыре цвета за линейное время
Новый алгоритм раскраски плоских карт в четыре цвета работает за линейное, а не квадратичное время: карта в 10 раз больше требует в 10 раз больше расчётов, а не в 100.

Международная группа исследователей, включая Миккеля Торупа из Копенгагенского университета и Карстена Томассена из Технического университета Дании, представила на конференции Foundations of Computer Science (FOCS) новый алгоритм раскраски плоских карт в четыре цвета, сообщает pravda.ru pravda.ru
pravda.rupravda.ruОткрыть источник ↗. Время его работы растёт линейно с размером карты, тогда как прежние алгоритмы масштабировались квадратично. Это не новое доказательство теоремы четырёх цветов, а поиск оптимального способа её реализации.
Теорема и проблема скорости
Тезис о том, что для любой плоской карты достаточно четырёх цветов, сформулировал Фрэнсис Гатри в 1852 году. Первое доказательство, найденное в 1879 году, оказалось ошибочным, а окончательный ответ получили только в 1976 году с помощью компьютерной программы. Теорема считается решённой, но существовал разрыв между знанием того, что раскраска возможна, и наличием быстрого способа её построить.
У прежних алгоритмов время вычислений росло квадратично. Если число регионов увеличивалось в 10 раз, расчёт занимал в 100 раз больше времени, что осложняло работу с большими массивами данных.
Редуцируемые конфигурации как отправные точки
Исследователи работали с планарными графами: это совокупности точек и соединяющих их линий. В таких графах есть так называемые редуцируемые конфигурации, то есть определённые комбинации связей, которые можно использовать как отправные точки для раскраски pravda.ru
pravda.rupravda.ruОткрыть источник ↗. Томассен называет их «ручками», за которые можно ухватиться, чтобы начать заполнение цветом.
Главный результат команды в том, что таких «ручек» в графах гораздо больше, чем считалось ранее. Вместо последовательной раскраски алгоритм находит множество таких точек одновременно и заполняет области параллельно. Это переводит сложность вычислений из квадратичной в линейную: карта в 10 раз больше замедляет расчёт в 10 раз, а не в 100.
Исследователи отмечают, что подход работает и для поверхностей с отверстиями, например для объектов по форме вроде тора или куска сыра с дырками. Торуп иронично называет задачу «болезнью четырёх цветов». По сообщению издания, решение даёт новые инструменты для других сложных математических задач, где нужен быстрый перебор вариантов и поиск оптимальных структур.


