一个图中的路线问题：最小化平均边成本而非总成本。

Question

一个图中的路线问题：最小化平均边成本而非总成本。

algorithmoptimizationgraphgraph-theoryshortest-path

14

我有一个带权重的图，没有负权重，并且我想找到从一个节点到另一个节点的路径，尝试最小化单步的成本。我不需要最小化行程的总成本（例如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

这个问题是否有已知的算法？

感谢您的提前回复。

Eugenio

作为对templatetypedef答案的编辑。

一些问题：

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约束。

- Eugenio

3个回答

2

对于您的新问题，存在从哈密顿路径问题的规约（使您的问题难以处理）。取一个哈密顿路径实例（即，假定边缘的权重为单位），添加源和汇点顶点，并从源到所有其他顶点和从汇点到所有其他顶点添加权重为2的边缘。设置K = |V| + 2，并请求从源到汇点的路径。当且仅当最佳平均边长为(|V|+3)/(|V|+2)时，存在哈密顿路径。

请告诉我们您需要这些路径的原因，以便我们可以建议合理的近似策略。

- comestibles

0

你可以稍微修改Bellman-Ford算法，以使用最多K条边/节点来查找最小路径。如果边的数量是固定的，则必须最小化总成本，因为平均成本将是TotalCost/NumberOfEdges。

其中一种解决方案是从1到K迭代NumberOfEdges，找到最小的总成本并选择最小的TotalCost/NumberOfEdges。

- Hypuk

你必须小心处理这个问题，因为Bellman-Ford迭代跟踪的路径长度最多为k，所以仅仅在进行了k次Bellman-Ford迭代之后找到最小成本路径并不能一定给出正确答案。请参考我的解决方案以了解如何修复这个问题。 - templatetypedef

嗨@Hypuk，感谢您的回答，我不确定自己是否已经清楚地表达了问题。目前我正在使用Bellman-Ford算法，但我得到的路径太短，每条边的成本也太高了......我希望能够得到一条更长的路径（更多的边，每条边的成本更少），但如果我只是将“最多使用K条边”作为规则，那么我现在得到的结果会是一样的，对吧？ - Eugenio

抱歉，我正在使用Floyd-Warshall算法而不是Bellman-Ford。 - Eugenio

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

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

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

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

我们可以通过已知长度为m的路径来推断长度为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，然后使用上述递推式和动态规划来计算BF(s，t，n)的值。其总运行时间为O(EV)，因为每步需要考虑E条边并且总共有V个顶点。

让我们看看如何修改此算法以解决您的问题。首先，要将其限制为长度为k的路径，我们只需在找到长度不超过k的所有最短路径后截断Bellman-Ford迭代。要找到具有最低平均成本的路径有点棘手。在每个节点，我们将跟踪两个量-到达节点t的最短路径长度和该路径的平均长度。在考虑可以到达t的新路径时，我们的选择是保留我们找到的早期路径（其成本由到目前为止的最短路径除以其中的节点数给出）或将某些其他路径扩展一步。然后，该路径的新成本由之前的总成本加上边长除以旧路径中的边数加一给出。如果我们选择其中最便宜的并记录其成本和边数，则最终我们将在时间O(kE)内计算出长度不大于k的最低平均成本的路径。作为初始化，我们将说从起始节点到自身的路径长度为0，平均成本为0（平均成本无关紧要，因为无论何时我们将其乘以边数，我们得到的都是0）。我们还将说每个其他节点的距离为无穷大，方法是将边的平均成本设为无穷大并且边数为1。这样，如果我们尝试计算由路径扩展形成的路径的成本，它将似乎具有平均成本无穷大，并且不会被选择。

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

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++;
        }
    }
}

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

希望这可以帮助您！