Проблема с прокладкой пути / дороги

Question

Сегодня мы получили задание, которое нужно выполнить в лаборатории (через два часа).Вопрос заключался в следующем:

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Надеюсь, это дает некоторый полезный контекст.

Answer 3

Есть аспект описания проблемы, который мне не ясно:

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

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

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

Answer 4

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

1. Представляют матрицу m как график g с v = {mij | i <= m, j <= n}, e = {(mi1j1, mi2j2): i1, i2 <= m, j1, j2 <= n, | i1-i2 | = 1-эксклюзивный или | J1-J2 | = 2}

2. Возьмите набор B входов, установить H залов

3. H '= h / b, b' = b / h (отметьте входы залы, они достигаются на глубине 0, удалите все эти входы, как это залы)

4. Сделать ширину, первый обход. На каждой глубине отметьте залы, которые могут быть достигнуты от B, пока все залы не помечены. Выберите соответствующие пути.

Answer 5

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