Подключение непересекающихся множеств в 2D-массиве

Question

Я пытаюсь создать случайную сетку с позициями, которые являются обходными и непереходными, и убедитесь, что существует путь от одной позиции перемещения к любой другой точке пересечения в одном из 4-х направлений { Вправо, Вверх, Влево, Вниз}. Проходимые позиции представлены как «[]» и Non-проходимые позиции представлены как «[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-hard. Вы можете получить хорошее приближение, учитывая, что ваши графики плоские: http://www-math.mit.edu/~hajiagha/NodePlanarSteiner.pdf.