Как минимизировать общую стоимость дерева кратчайшего пути
У меня есть направленный граф без петель с положительным весом ребра. Это имеет единственный источник и ряд целей (вершины дальше всего от источника). Я нахожу кратчайшие пути от источника до каждой цели. Некоторые из этих путей перекрытие. То, что я хочу, является деревом кратчайшего пути, которое минимизирует полную сумму весов по всем краям.
Например, рассмотрите две из целей. Учитывая весь равный вес ребра, если они совместно используют единственный кратчайший путь для большей части своей длины, затем это предпочтительно для двух главным образом неперекрывающихся кратчайших путей (меньше краев в дереве равняется более низкой общей стоимости).
Другой пример: два пути не накладываются для небольшой части их длины, с высокой стоимостью для неперекрывающихся путей, но низкой стоимостью для длинного общего пути (низко объединенная стоимость). С другой стороны, два пути не накладываются для большей части их длины, с низкой стоимостью для неперекрывающихся путей, но высокой стоимостью для короткого общего пути (также, низко объединенная стоимость). Существует много комбинаций. Я хочу найти, что решения с самой низкой общей стоимостью, учитывая все кратчайшие пути из источника предназначаются.
Другими словами, я хочу самое короткое, деревья кратчайшего пути.
Это звонит в какие-либо звонки с кем-либо? Кто-либо может указать на меня на соответствующие алгоритмы или аналогичные приложения?
Удачи!
2 ответа
Если у вас есть только положительные затраты и вы их минимизируете, просто используйте алгоритм Дейкстры .
Эта задача (Дерево Штейнера) является NP-трудной и максимально SNP-полной, поэтому не существует ни алгоритмов полиномиального времени, ни PTAS (произвольно близких приближений), если только P = NP.
MST может дать вес, произвольно худший, чем оптимальный, если только вы не знаете какую-то особенность вашего графа (например, что граф планарный, или, по крайней мере, что веса подчиняются неравенству треугольника). Например, если у вас есть K_1,000,000,001 со всеми весами ребер 1 и только одной целью, оптимальное решение имеет вес 1, а MST - вес 1,000,000,000.
Если предположить, что все ребра между целями и все ребра между источником и каждой целью существуют, то все равно можно проскочить на произвольный коэффициент.
Конечно, вы можете преобразовать граф, чтобы "удалить" большие веса ребер за время O(E) или около того, обходя граф. Это плюс MST множества целей и источников дает коэффициент аппроксимации 2.
Существуют и лучшие коэффициенты аппроксимации. Robins & Zelikovsky имеют алгоритм полиномиального времени, который никогда не бывает хуже оптимального более чем на 54.94%: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf
Хлебик и Хлебикова показывают, что аппроксимация ближе 1.05% является NP-трудной: Проблема дерева Штейнера на графах: Inapproximability results (doi 10.1.1.4.1339)
Если ваш граф планарный, ситуация лучше. Существует быстрый алгоритм, дающий произвольно близкое приближение, предложенный Боррадайлом, Кеньоном-Матье и Клейном (на основе Эриксона, Монма и Вейнотта): Схема аппроксимации O(nlogn) для дерева Штейнера в планарных графах (doi 10.1.1.133.4154)