Проблема пути/дорожного покрытия

Сегодня у нас есть задание пройти в лаборатории (через два часа). Вопрос был:

Вам предоставляется матрица m * n.
В матрице есть жилые залы "h" и "основные" входы в здание.
Расположение этих "h" залов и "b" входов известно (в терминах (x, y)).
Вам нужно проложить тропы, чтобы каждый жилый зал имел хотя бы один способ добраться до одного из входов "b".
Может быть не более 'b' таких отключенных путей.
Длина пути должна быть минимальной.
Вы можете перемещаться только вверх, вниз, влево или вправо.
Решение не должно быть попыткой грубой силы.

Назначение завершено. Но я все еще думаю, как это будет решено. Существует ли стандартный термин для таких проблем? Что я должен прочитать?

Используют ли люди такие алгоритмы для прокладки дорог в городах?

Ответ 1

Вот решение, которое я придумал. Он не генерирует отключенные пути "b". Он генерирует один путь, который проходит через все жилые залы и входы.

Рассчитайте расстояние между каждой парой узлов (разность X координат + разность координат Y). Теперь у вас есть полный график.
Найти MST для этого полного графика
Каждый наклонный край MST (не вертикальный или горизонтальный) можно разделить на две части - горизонтальную и вертикальную.
Каждый раскол может быть выполнен двумя способами: сначала горизонтальный, затем вертикальный или наоборот.
Пройдите через каждую такую перестановку и вычислите путь с наименьшей длиной. Это ответ.

Ответ 2

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

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

С другой стороны, у вас есть моделирование конкретных областей города, города, обмена и т.д. Это числовые модели, которые рассматривают каждый автомобиль как автономный агент с такими факторами, как агрессия, знание дорог и т.д. Это очень простой подход с использованием грубой силы, но это единственный способ предоставить полезную статистику фактического поведения трафика в сложной сети с такими функциями, как светофоры, шины и т.д. Модель трафика может, например, подключить ее к фактические данные управления трафиком, запустить модель на определенный период для конкретных проектных решений и настроить ее на 6 или 7 раз. Полученные данные дают вам очень хорошую оценку эффективности конкретного решения против другого (или статус-кво).

Надеемся, что это дает некоторый полезный контекст.

Ответ 3

В этом аспекте описания проблемы мне не ясно:

Когда вы говорите: "Вам нужно проложить путь", означает ли это "только один связанный путь"? Или может быть несколько отключенных путей? (например, путь от зала H1 до входа в здание B1 и отдельный путь от зала H2 до входа в здание B2).

Но, однако, вы отвечаете на мой вопрос, это чрезвычайно сложная проблема: она NP-hard, поскольку включает в себя прямолинейную проблему Штайнера как специальный случай (когда есть только один главный вход в здание).

Поэтому никто не знает, как эффективно решить его в общем случае!

Ответ 4

Я думаю, что проблема проще, а не дерево Штейнера или даже минимальное связующее дерево.

Представить матрицу M в виде графа G с V = {Mij | я <= m, j <= n}, E = {(Mi1j1, Mi2j2): i1, i2 <= m, j1, j2 <= n, | i1-i2 | = 1-exclusive OR | j1-j2 | = 2}
Возьмите множество В входов, установите H залов
H '= H/B, B' = B/H (отметьте входы, которые находятся в входах, они достигаются на глубине 0, удаляют все эти входы, поскольку это залы)
Пройдите в ширину в первый раз. На каждой глубине отметьте залы, которые могут быть достигнуты от B до тех пор, пока не будут отмечены все залы. Выберите соответствующие пути.

Ответ 5

Это проблема поиска. Вы должны были сделать это через 2 часа, верно? Я бы DFS и обрезать. Вы можете использовать эвристику, чтобы быстрее перейти к лучшим решениям. Но имейте в виду, что эвристика не может гарантировать оптимальные решения, поэтому вам придется попробовать все возможности. Кажется, что NP-жесткий.