Цифра › Софт2 мин чтения

Торуп и Томассен представили на FOCS алгоритм раскраски карт в четыре цвета за линейное время

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

Thorup, Thomassen and colleagues present a linear-time four-colouring algorithm for planar maps at FOCS
Фото: pravda.ru

Международная группа исследователей, включая Миккеля Торупа из Копенгагенского университета и Карстена Томассена из Технического университета Дании, представила на конференции Foundations of Computer Science (FOCS) новый алгоритм раскраски плоских карт в четыре цвета, сообщает pravda.ru pravda.rupravda.rupravda.ruОткрыть источник ↗. Время его работы растёт линейно с размером карты, тогда как прежние алгоритмы масштабировались квадратично. Это не новое доказательство теоремы четырёх цветов, а поиск оптимального способа её реализации.

Теорема и проблема скорости

Тезис о том, что для любой плоской карты достаточно четырёх цветов, сформулировал Фрэнсис Гатри в 1852 году. Первое доказательство, найденное в 1879 году, оказалось ошибочным, а окончательный ответ получили только в 1976 году с помощью компьютерной программы. Теорема считается решённой, но существовал разрыв между знанием того, что раскраска возможна, и наличием быстрого способа её построить.

У прежних алгоритмов время вычислений росло квадратично. Если число регионов увеличивалось в 10 раз, расчёт занимал в 100 раз больше времени, что осложняло работу с большими массивами данных.

Редуцируемые конфигурации как отправные точки

Исследователи работали с планарными графами: это совокупности точек и соединяющих их линий. В таких графах есть так называемые редуцируемые конфигурации, то есть определённые комбинации связей, которые можно использовать как отправные точки для раскраски pravda.rupravda.rupravda.ruОткрыть источник ↗. Томассен называет их «ручками», за которые можно ухватиться, чтобы начать заполнение цветом.

Главный результат команды в том, что таких «ручек» в графах гораздо больше, чем считалось ранее. Вместо последовательной раскраски алгоритм находит множество таких точек одновременно и заполняет области параллельно. Это переводит сложность вычислений из квадратичной в линейную: карта в 10 раз больше замедляет расчёт в 10 раз, а не в 100.

Исследователи отмечают, что подход работает и для поверхностей с отверстиями, например для объектов по форме вроде тора или куска сыра с дырками. Торуп иронично называет задачу «болезнью четырёх цветов». По сообщению издания, решение даёт новые инструменты для других сложных математических задач, где нужен быстрый перебор вариантов и поиск оптимальных структур.

Источники · 1

Нашли ошибку?
  1. ↩

Читайте также

Далее

Следующая статья откроется сама

Ещё
Мы в соцсетях

Введите хотя бы две буквы — результаты появятся сразу

↑↓выбрать↵открытьescзакрыть