图表中的路径问题:最小化平均边缘成本而不是总成本

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

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

提前致谢.

欧亨尼奥

编辑为templatetypedef的答案.一些问题:

1)事实上它可能多次采取一个周期来降低平均值对我的问题不利:也许我应该提到它但我不想多次访问同一个节点

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

3)当你说O(kE)时,你是指整个算法还是只是附加部分？

让我们在C中采用这个简单的实现,其中n =节点数e =边数,d是具有距离的向量,具有前驱的pa向量和结构边(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基于以下动态编程重现,试图找到从一些起始节点到另一个节点的最短路径,对于某些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.如果我们采用最便宜的这些,然后记录其成本和边缘数量,最后我们将计算具有最小平均成本长度不大于k的时间O(kE)的路径.作为初始化,我们将说从起始节点到其自身的路径长度为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难的,所以除非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这些方程中的变量替换为缓存的路径长度来更新代码.

希望这可以帮助!

Answer 2

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

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