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

Ответ 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-жесткий.