algorithm - 图中的路线问题 : minimize average edge cost instead of total cost

Question

我有一个加权图，没有负权重，我想找到从一个节点到另一个节点的路径，试图最小化单个步骤的成本。我不需要最小化旅行的总成本(例如 Dijkstra 所做的)，而是最小化平均步骤成本。但是，我有一个约束:K，路径中的最大节点数。

因此，例如从 A 到 J 可能 Dijkstra 会找到这条路径(括号之间的权重)

A (4) D (6) J -> total cost: 10

我需要的算法，设置 K = 10，会找到类似的东西

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15

这个问题有没有众所周知的算法？

提前致谢。

欧亨尼奥

编辑为模板类型定义的答案。
一些问题:

1) 可能需要多次循环才能降低平均值这一事实对我的问题不利:也许我应该提到它，但我不想多次访问同一个节点

2)是否可以利用我没有负权重的事实？

3) 当您说 O(kE) 时，您是指整个算法还是仅指附加部分？

让我们在 C 中采用这个简单的实现，其中 n=节点数 e=边数，d 是一个带有距离的向量，p 是一个带有前驱的向量，一个结构边 (u,v,w) 记住图中的边

for (i = 0; i < n; ++i)
    d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        for (j = 0; j < e; ++j)
            if (d[edges[j].u] + edges[j].w < d[edges[j].v]){
                d[edges[j].v] = d[edges[j].u] + edges[j].w;
                p[edges[j].v] = u;
                }

我不确定应该如何根据您的回答修改代码；考虑平均成本而不是总成本是否足够？

for (i = 0; i < n; ++i)
        d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        steps = 0;
        for (j = 0; j < e; ++j)
            if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
                d[edges[j].v] = d[edges[j].u] + edges[j].w;
                p[edges[j].v] = u;
                steps++;
            }

但无论如何我不知道如何同时考虑 K 限制......再次提前感谢您的帮助。

编辑
由于我可以承受一些错误，我正在考虑这个天真的解决方案:

预先计算所有最短路径并记住A

在修改后的图上预先计算所有最短路径，我在其中切割一定权重的边并将它们内存在 B

中

当我需要一条路径时，我会查看 A，例如从 x 到 y 这是路径
x->z->y
然后对于我在 B 中查看的每一步，
所以对于 x > z 我看看 B 中是否有连接，如果没有，我保留 x > z 否则我用 B 提供的子路径填充路径 x > z，这可能类似于 x->j->h- > z;然后我对 z->y 做同样的事情。
每次我也会检查我是否添加了循环路径。

也许我会得到一些奇怪的路径，但它可以在大多数情况下工作。
如果我尝试使用不同的“切割阈值”扩展解决方案，也许我也可以接近尊重 K 约束。

Answer 1

我相信您可以使用 Bellman-Ford 算法的修改版本来解决这个问题。

Bellman-Ford 基于以下动态规划递归，试图找到从某个起始节点 s 到其他节点的最短路径，对于某些 m，长度不大于 m。作为基本情况，当您考虑长度为零的路径时，唯一可到达的节点是 s 并且初始值为

BF(s, t, 0) = infinity
BF(s, s, 0) = 0

然后，如果我们知道长度为 m 的路径的值，我们可以通过注意到旧路径可能仍然有效，或者我们想将某个路径扩展长度为 1 来找到长度为 m + 1 的路径的值:

BF(s, t, m + 1) = min {
                     BF(s, t, m),
                     BF(s, u, m) + d(u, t) for any node u connected to t
                   }

整个算法通过注意任何最短路径的长度必须不大于 n 来工作，然后使用上述递归和动态规划来计算所有 t 的 BF(s, t, n) 值。它的总运行时间是 O(EV)，因为在每一步都有 E 条边需要考虑，并且总共有 V 个顶点。

让我们看看我们如何改变这个算法来解决你的问题。首先，为了将其限制为长度为 k 的路径，我们可以在找到所有长度为 k 以内的最短路径后切断 Bellman-Ford 迭代。找到平均成本最低的路径有点棘手。在每个点，我们将跟踪两个量——到达节点 t 的最短路径的长度和该路径的平均长度。在考虑可以到达 t 的新路径时，我们的选择是保留我们找到的较早路径(其成本由迄今为止的最短路径除以其中的节点数给出)或将其他路径扩展一步。然后，该路径的新成本由之前的总成本加上边长除以旧路径中的边数加 1 得出。如果我们取这些中最便宜的，然后记录其成本和边数，最后我们将计算出在时间 O(kE) 内长度不大于 k 的最低平均成本的路径。作为初始化，我们会说从起始节点到自身的路径长度为 0，平均成本为 0(平均成本无关紧要，因为每当我们将其乘以边数时，我们就会得到 0)。我们还将通过说一条边的平均成本是无穷大并且边的数量是一条来说每个其他节点都在无穷远处。这样，如果我们尝试计算通过扩展路径形成的路径的成本，它将看起来具有无穷大的平均成本并且不会被选中。

从数学上讲，解决方案如下所示。在每个点，我们存储平均边成本和每个节点的边总数:

BF(s, t, 0).edges = 1
BF(s, t, 0).cost  = infinity

BF(s, s, 0).edges = 0
BF(s, s, 0).cost  = 0

BF(s, t, m + 1).cost = min {
    BF(s, t, m).cost,
    (BF(s, u, m).cost * BF(s, u, m).edges + d(u, t)) / (BF(s, u, m).edges + 1)
}

BF(s, t, m + 1).edges = {
    BF(s, t, m).edges         if you chose the first option above. 
    BF(s, u, m).edges + 1     else, where u is as above
}

请注意，这可能找不到长度为 k 的简单路径，因为最小化平均成本可能需要您多次采用低(正或负)成本的循环来降低平均值。例如，如果一个图有一个零成本循环，你应该尽可能多地继续使用它。

编辑 :针对您的新问题，如果您不想在路径上复制节点，则此方法将不起作用。正如@comestibles 所指出的，这个版本的问题是 NP-hard，所以除非 P = NP，否则你不应该期望找到任何好的多项式时间算法来解决这个问题。

至于运行时间，我上面描述的算法的总运行时间为 O(kE)。这是因为计算递归的每次迭代需要 O(E) 时间，并且总共有 k 次迭代。

最后，让我们看看您提出的代码。我在这里转载:

for (i = 0; i < n - 1; ++i) {
    steps = 0;
    for (j = 0; j < e; ++j) {
        if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
            d[edges[j].v] = d[edges[j].u] + edges[j].w;
            p[edges[j].v] = u;
            steps++;
        }
    }
}

你的第一个问题是如何考虑 k 。这可以很容易地通过重写外部循环来计数到 k，而不是 n - 1 来完成。 这给了我们这样的代码:

for (i = 0; i < k; ++i) {
    steps = 0;
    for (j = 0; j < e; ++j) {
        if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
            d[edges[j].v] = d[edges[j].u] + edges[j].w;
            p[edges[j].v] = u;
            steps++;
        }
    }
}

我注意到的一个问题是，修改后的 Bellman-Ford 算法需要让每个候选最佳路径独立存储其边数，因为每个节点的最佳路径可能会被不同数量的边到达。为了解决这个问题，我建议使用 d数组存储两个值 - 到达节点所需的边数和沿该路径的节点的平均成本。然后，您将通过替换 steps 来更新您的代码。这些方程中的变量与缓存的路径长度。

希望这可以帮助!