Минимизируйте длину путей, необходимых для соединения нескольких пунктов назначения

Question

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

Какой алгоритм может этого добиться?

Answer 1

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

minimize sum_{e in edges} length(e) x(e)
subject
x(e) in {0, 1}

, а затем

1. Используйте библиотеку для оптимального решения текущей программы.
2. Найдите связанные компоненты подграфаребер e с x(e) = 1.

3. Если все клеммы принадлежат одному подключенному компоненту, вернуть этот подграф.В противном случае для каждого подключенного компонента S, который содержит хотя бы один терминал, добавьте следующее ограничение.Вернитесь к шагу 1.

   sum_{e in edges such that one endpoint is in S and the other isn't} x(e) ≥ 1