#графы #cpp
Как точно называется задача для покрытия дорожной сетью?
Например есть такой неограф:
Вес дуг это расстояние между городами.
Применив минимальное остовное дерево получается такая картина:
Все вершины связаны в одну большую дорогу, но если перемещаться из Рязани в Казань(по
остовному дереву), то потребуется 3+7+7+3=20 шагов.
То есть данный вид связи подходит для телефонной сети, но не для дорожной.
А в идеале, должна быть еще дорога между Рязанью и Казанью.
То есть должны быть еще элементы оптимизации, где будет коэфицент зависимость стоимости
прокладки дороги по отношению к времени перемещения из городов(как то так).Чем выше
такой коэфицент тем больше дуг будет между вершинами.
Есть ли конкретная задача которая этим занимается?
Ответы
Ответ 1
В первой формулировке (без наложения вспомогательных 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], если у вас, конечно, много свободного времени :)
