Графы - дорожная сеть

#графы #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], если у вас, конечно, много свободного времени :)