Дана DAG, в которой каждый узел имеет числовое значение. Я хотел бы получить путь через граф, который имеет минимальную дисперсию значений узлов.
Напомним, какой алгоритм является лучшим для поиска пути с минимальной дисперсией в направленном ациклическом пути?
Спасибо, Пьеро
Из статьи: "Надежная маршрутизация: модель надежной связи"
Определение 6.7. Задача простого пути с минимальной дисперсией (MVSPP): для графа G = (V, E) с положительными весами вершин w(v) для каждой вершины v ∈ V и несмежными вершинами s, t ∈ V найдите s, t -путь p, который минимизирует дисперсию весов для набора вершин в p .
Предположим, что s, t не связаны напрямую одним ребром, так как тогда решение тривиально. Путь 〈s, t〉 имеет дисперсию 0 и является путем с минимальной дисперсией.
Теорема 6.8. Задача простого пути с минимальной дисперсией (MVSPP) является NP-сложной.
Вот что я узнал... Я думаю, что это отвечает на мой вопрос.
