Соединение непересекающихся множеств в двумерном массиве

Question

Я пытаюсь сгенерировать случайную сетку с позициями Traversable и Non-Traversable и убедиться, что есть путь от одной позиции Traversable к любой другой позиции Traversable в одном из 4 направлений {вправо, вверх, влево, вниз}. Проходные позиции представлены как "[ ]", а неходовые позиции представлены как "[X]"

Here is a grid I have generated: 
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][ ][X]
[ ][ ][X][ ][ ][ ][X][ ][ ][X][X][ ][ ][ ]
[X][ ][ ][ ][ ][X][X][X][ ][ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ][X][ ][ ][ ][X][ ][ ][X][ ]
[ ][X][ ][ ][ ][X][ ][ ][ ][ ][X][X][X][X]
[ ][ ][X][X][X][ ][ ][ ][X][X][X][X][X][X]
[ ][X][ ][ ][ ][X][ ][ ][ ][X][X][ ][ ][X]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][ ]
[ ][ ][X][ ][ ][ ][X][ ][X][X][ ][ ][ ][ ]
[ ][X][ ][X][ ][ ][ ][ ][ ][ ][X][X][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][X][ ][ ][X][X][ ]

Какой алгоритм я могу использовать, чтобы найти непересекающиеся множества в моей сетке и создать путь между непересекающимися множествами? Спасибо!

Answer 1

Чтобы найти непересекающиеся компоненты, вы можете использовать поиск в ширину (с очередью) или поиск в глубину (со стеком), начиная с любой перемещаемой позиции. Когда поиск прекращается, он помечает весь компонент. Затем, если есть неотмеченные позиции, используйте их в качестве отправных точек для другого поиска и т. Д., Пока вы не отметите все пройденные позиции.

Чтобы выяснить, какие непересекаемые позиции должны быть удалены, если вы хотите удалить (почти) как можно меньше, подумайте о каждом из "непересекающихся наборов" (лучше называть их "связанными компонентами") как отдельные узлы в график, и посмотрите на множество путей, соединяющих их. Подсчитайте количество X, которые должны быть удалены для каждого пути, соединяющего узел с другим узлом, и используйте это как вес ребра в графе. Затем вы хотите найти минимальное остовное дерево этого графа, используя, например, алгоритм Крускала.

Этот метод не гарантирует нахождение минимального количества X для удаления, чтобы соединить перемещаемые позиции; например, на графике, который вы дали, удаление одного X в верхнем правом углу соединяет три компонента, тогда как мое предложение может привести к удалению двух X. Тем не менее, ваша проблема определена неопределенно, поэтому я считаю, что разница не важна.

Чтобы найти точное минимальное количество X для удаления, вам нужно решить "проблему дерева Штейнера с взвешиванием по узлу", которая, как я думаю, в общем случае является NP-сложной. Возможно, вы сможете получить хорошее приближение, учитывая, что ваши графики плоские: http://www-math.mit.edu/~hajiagha/NodePlanarSteiner.pdf.