在有向无环图中找到最小方差路径

Question

给定一个 DAG，其中每个节点都有一个数值。我想通过图表获得节点值方差最小的路径。

回顾一下，在有向无环路径中找到最小方差路径的最佳算法是什么？

谢谢，皮耶罗

Answer 1

来自论文："Routing with Confidence: A Model for Trustworthy Communication"

定义 6.7。最小方差简单路径问题 (MVSPP)：给定一个图 G = (V, E)，每个顶点 v ∈ V 和非相邻顶点 s, t ∈ V 具有正顶点权重 w(v)，找到一个 s, t - 最小化 p 中顶点集的权重方差的路径 p .

我们假设 s、t 不直接由单条边连接，因为那样解是微不足道的。路径 方差为 0，是方差最小的路径。

定理 6.8。最小方差简单路径问题 (MVSPP) 是 NP-hard。

这是我发现的...我认为这回答了我的问题。