3

Как точно называется задача для покрытия дорожной сетью?

Например есть такой неограф:

alt text

Вес дуг это расстояние между городами.

Применив минимальное остовное дерево получается такая картина: Все вершины связаны в одну большую дорогу, но если перемещаться из Рязани в Казань(по остовному дереву), то потребуется 3+7+7+3=20 шагов. alt text

То есть данный вид связи подходит для телефонной сети, но не для дорожной. А в идеале, должна быть еще дорога между Рязанью и Казанью.

alt text

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

Есть ли конкретная задача которая этим занимается?

3
  • Задача коммивояжёра. Нет?
    – nicolai
    28 окт 2013 в 20:09
  • 2
    @nicolai, нет. Задача коммивояжера заключается не в построении графа, а в отыскании самого выгодного маршрута на исходном графе, проходящего через все города хотя бы по одному разу и с последующим возвратом в исходный город.
    – Shad
    28 окт 2013 в 20:16
  • Хм. Ну это в любом случае задача поиска оптимального подграфа. Если вы сумеете сформулировать условие оптимальности, может быть, это окажется одной из классических задач. (Но я не спец.)
    – VladD
    28 окт 2013 в 21:08

1 ответ 1

8
  • В первой формулировке (без наложения вспомогательных constraint'ов на стоимость строительства дорог) это — задача нахождения Shortest total path length spanning tree [1], для которой доказано, что она NP-трудная. Решить эту задачу можно с помощью приближенных алгоритмов (см., например, первую ссылку).

  • Для такой же задачи, где стоимость постройки дороги не связана с длиной дороги, это будет задача нахождения "Constrained shortest total path length spanning tree".

  • Нестрого говоря, эта задача не проще предыдущей, поэтому тоже является NP-трудной. Если формально это доказывать, наверно, нужно сделать такой же переход, как сделали вот здесь [2] при переходе от задачи Minimum Spanning Tree → Constrained Minimum Spanning Tree.

  • Думаю, что для приближенного решения этой задачи можно придумать, как совместить подходы [1] и [2], если у вас, конечно, много свободного времени :)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.