Оптимизация алгоритма подключения к 2D-сетке

Резюме: я ищу оптимальный алгоритм для обеспечения связи через двумерную сетку двоичных значений. У меня есть довольно сложный алгоритм, который делает это за линейное время, но только при выполнении определенных шагов предварительной обработки. Ниже приведены довольно подробные сведения об алгоритме и времени его выполнения. Я также собрал приложение Unity, которое предлагает подробную визуализацию всех шагов, упомянутых ниже (и некоторых других), которые можно найти здесь.

У меня есть набор скриптов, которые процедурно генерируют ландшафт, используя алгоритм, называемый марширующими квадратами. Один из шагов - соединить все регионы вместе. В частности, у меня есть сетка из нулей (этажей) и единиц (стены), и я хочу, чтобы каждый 0 был достижим из любого другого 0. Я оптимизирую для:

• Объем туннелирования, который необходимо сделать. то есть количество единиц, которые превращаются в 0, должно быть минимизировано.
• Асимптотическое время выполнения. Я пытаюсь сделать его линейным по количеству плиток в сетке или максимально приближенным к линейному.

Рассматривая комнаты (связанные области нулей) как вершины, а потенциальные туннели как ребра, мы можем использовать алгоритм минимального остовного дерева в качестве нашей рабочей лошадки. Я опишу алгоритм с начальной точки несвязанной сетки из нулей и единиц.

Ввод:

Двумерный массив байтов, 0 или 1, представляющий местность (0: пол, 1: стена).

например следующий имеет четыре «комнаты» (соединенные компоненты этажей).

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 
1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 
1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 
1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 
1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 
1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 
1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 
1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Вывод

Та же сетка, так что в каждую комнату можно попасть из любой другой комнаты, с наименьшим количеством повреждений, нанесенных сетке (наименьшее количество единиц заменено на 0). Всего мы проложили три туннеля:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 
1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 
1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 
1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 
1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 
1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 
1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Обзор базового алгоритма:

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

1. Запустите BFS в сетке, чтобы найти комнаты (соединенные компоненты этажей), сохраняя только краевые плитки (то есть плитки пола, смежные с плиткой стены), поскольку кратчайший путь между двумя комнатами всегда будет между двумя краевыми плитками.

2. Для каждой пары комнат сделайте двойной цикл, чтобы найти пару плиток с кратчайшим евклидовым расстоянием. Эта пара образует потенциальный туннель между двумя комнатами, прокладывая между ними прямой путь.

3. Рассматривайте комнаты из (1) как вершины, а пары из (2) как рёбра в графе с весами как евклидово расстояние. Запустите алгоритм минимального связующего дерева Краскала на этом графике, чтобы получить список туннелей, которые нужно выкопать, которые минимизируют количество плиток, которые необходимо изменить.

Это гарантирует возможность подключения и гарантирует абсолютное минимальное количество измененных плиток (предостережение: это неверно, если мы рассматриваем возможность подключения комнаты не к другой комнате, а к туннелю между другой парой комнат). Проблема в том, что он плохо масштабируется: шаг (2) масштабируется квадратично по количеству плиток в сетке.

Оптимизированный алгоритм

Узкое место связано с этапом (2). Мы тщательно проверяем каждую пару плиток для каждой пары комнат, чтобы обеспечить минимальное соединение. Если мы допускаем небольшую ошибку (например, неоптимальное соединение), мы можем значительно ускорить ее. Основная идея состоит в том, чтобы пропустить количество плиток, пропорциональное только что вычисленному нами расстоянию: если мы вычислим большое расстояние между плиткой A и плиткой B, то есть вероятность, что мы далеки от оптимального соединения, поэтому мы можем пропустить проверку рядом плитки. Любая ошибка из-за этого пропуска будет пропорциональна длине оптимального соединения.

Чтобы объяснить это наглядно, предположим, что X и Y представляют собой текущую пару проверяемых плиток, и что в настоящее время мы проводим X по комнате слева.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 X 0 0 0 0 0 0 1 1 1 1 1 1 1 
1 1 0 0 0 0 0 0 0 1 1 1 1 1 1
1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 
1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 
1 1 1 1 1 1 1 0 0 0 0 Y 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Расстояние между ними 11, поэтому пропустим 11 плиток (отмечены тире):

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 0 - - - - - - 1 1 1 1 1 1 1 
1 1 0 0 0 0 0 - - 1 1 1 1 1 1
1 1 0 0 0 0 - - 1 1 1 1 1 1 1 
1 0 0 0 0 X - 1 1 1 1 0 0 0 1 
1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 
1 1 1 1 1 1 1 0 0 0 0 Y 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

Большинство сравнений будут далеко друг от друга, поэтому это резко сокращает время выполнения шага 2 и на практике дает минимальную ошибку.

Единственная проблема, которую здесь упускают из виду, заключается в том, что здесь предполагается, что краевые плитки упорядочены: это требует дополнительного этапа предварительной обработки.

Итак, вот оптимизированный алгоритм:

1. Выполните BFS, как в предыдущем алгоритме.

2. Отсортируйте каждую комнату. Это можно сделать, выполнив сначала в глубину краевые плитки. Это даст нам примерно непрерывный путь вдоль края комнаты. Есть несколько (буквальных) угловых случаев, когда путь может перескакивать, но пути непрерывны в разумном приближении.

3. Выполните двойной цикл на шаге 2 из предыдущего алгоритма, но на этот раз вместо увеличения на одну плитку увеличьте расстояние на последнее вычисленное расстояние.

4. Выполните алгоритм Краскала, как прежде. Обратите внимание, что метод Крускала требует отсортировать ребра в графе: поскольку граф полный (каждая пара комнат имеет потенциальный туннель), стандартная сортировка становится новым узким местом в алгоритме. Поскольку мы выполняем сортировку по расстоянию, которое является числом с плавающей запятой, мы можем добиться более быстрой сортировки, усекая числа с плавающей запятой и превращая их в целые числа. Опять же, это дает минимальную ошибку (например, Kruskal может выбрать туннель с расстоянием 4,6 вместо туннеля с расстоянием 4,2), но обеспечивает резкое ускорение.

Анализ времени выполнения

Пусть n обозначает количество плиток в сетке. Обозначим через m количество комнат (связанных компонентов) в сетке. Обратите внимание, что в худшем случае m = O (n).

Алгоритм состоит из четырех шагов. (1) и (2) - это O (n) по памяти и времени, поскольку они являются BFS и DFS, которые обрабатывают каждый тайл на карте не более одного раза.

(3) немного сложнее. Мы делаем двойной цикл по каждой комнате, а затем находим соединение. Это O (m ^ 2) для двойного контура, умноженное на среднее количество работы, выполненной на пару комнат. Установить жесткую аналитическую границу для работы, выполняемой в среднем на пару комнат, непросто. Но эмпирически, тестируя большое количество разнообразных конфигураций, по мере увеличения n средняя работа сходится к единственному сравнению. Это связано с тем, что среднее расстояние плиток между комнатами увеличивается по мере роста сетки.

Таким образом, в целом работа, проделанная для (3), составляет O (m ^ 2) с объемом памяти O (1).

Для (4) он задается средой выполнения для Kruskal, которая составляет O (m ^ 2 logm ^ 2) для наивной сортировки ребер и O (m ^ 2 a (m ^ 2)) для прогона ребер через данные UnionFind. структура, где a - обратная функция Аккермана (фактически постоянная). Если мы усечем длины ребер и воспользуемся целочисленным алгоритмом сортировки, мы сможем уменьшить сортировку до O (m ^ 2). Память O (м ^ 2).

Таким образом, в целом во время выполнения преобладает алгоритм Крускала, задаваемый O (m ^ 2 a (m ^ 2)), или, по сути, O (m ^ 2). Учитывая, что в худшем случае m = O (n), это не очень хорошая производительность. Но мы можем сделать последний шаг предварительной обработки в сетке, чтобы уменьшить ее до O (n), то есть естественным образом ограничить количество комнат.

Перед любыми другими шагами мы можем использовать алгоритм заливки для заполнения небольших комнат за линейное время: в частности, мы можем заполнить любую комнату размером меньше sqrt (n). Поскольку в сетке может быть не более sqrt (n) комнат размером не менее sqrt (n), из этого следует, что m = O (sqrt (n)), что делает весь алгоритм линейным по размеру сетки.

Заключение

Можно ли сделать лучше, чем это? Очевидно, что мы не можем работать асимптотически лучше, чем линейное время и память, но для достижения этих цифр допускается некоторая неаккуратная количественная оценка субоптимальности в длинах туннелей, и это требует изменения исходной сетки (а именно, ограничения числа комнат).