Обеспечение сильно связанного орграфа

Контекст

Я создаю 3d-игру, используя процедурное поколение. Я пытаюсь подключить несколько предварительно сгенерированных комнат таким образом, чтобы независимо от того, игрок всегда может добраться до любой другой комнаты на карте. В номерах есть "возможные точки входа", к которым должны быть подключены соединительные коридоры. Однако не все точки входа доступны из всех других точек входа в комнату. Например, может быть ловушка для ямы, поэтому игрок на дне не сможет проехать через комнату наверху и должен будет найти другой способ.

Проблема

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

Пока работаем

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

Кто-нибудь знает лучший метод решения этой проблемы?

Ответ 1

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

Для 2-приближенного решения в полиномиальном времени: выберите произвольную корневую вершину, затем используйте алгоритм из-за Чу-Лю, а также Edmonds для вычисления минимально-затратных корневых и листообразных абажуров. Верните союз этих. Это 2-аппроксимация, потому что каждый сильно связанный дуговый подграф содержит как корневую, так и листообразную зазубренность (хотя и не обязательно минимальную стоимость). Теперь я вижу из одной из ваших ссылок, что Кейт Рэндалл также имела эту идею.

Существует множество эвристик, которые вы могли бы реализовать. Они могут работать неплохо, но они меня не интересуют. Если вы беспокоитесь о том, что они плохо себя ведут, тогда вы можете "запереть" их с упомянутым выше 2-приближением.

Если вы действительно хотите оптимальное решение, то ваш лучший выбор - это, вероятно, цельное программирование. Сформулированная как целочисленная программа, эта проблема имеет некоторое сходство с TSP. Программа для TSP выглядит следующим образом.

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
(-) for all v, sum_{v -> w} x(v -> w) = 1
(-) for all w, sum_{v -> w} x(v -> w) = 1
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

Для вашей проблемной программы мы отбрасываем ограничения, отмеченные (-), что заставило бы выбранные дуги быть гастролями.

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

Двойственность этой программы следующая.

maximize sum_{subsets S of vertices} y(S)
subject to
for all v -> w, sum_{subsets S of vertices, v in S, w not in S} y(S) <= cost(v -> w)
for all subsets S of vertices, y(S) >= 0

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

Ответ 2

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

Если вы просто подсчитываете ребра, а не их длины, то решение для планарных графов (этажей) в изоляции будет трансформировать это в несколько эвклидовых проблем дерева Штейнера, который, хотя и NP-hard, может быть решен с помощью почти оптимальной схемы приближения полиномиального времени. Тем не менее, вы упомянули, что хотите минимизировать общую длину путей, что делает это прямолинейной проблемой дерева Штейнера. Многое исследование было сделано по этой проблеме из-за ее применимости к проектированию схем. Существуют аппроксимации, которые могут быть в пределах 1,5 от оптимальных, которые могут работать лучше для того, что вы делаете: немного больше коридоров, а не всех входов в одном месте.