图中的路线问题：最小化平均边缘成本而不是总成本
我有一个加权图，没有负权重，我想找到从一个节点到另一个节点的路径，试图最小化单步骤的成本。 我不需要将行程的总成本最小化（例如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极限......再次感谢您的帮助。
编辑由于我可以承受一些错误，我正在考虑这个naif解决方案：
当我需要一条路径时，我看着A，例如从x到y这是路径x-> z-> y然后对于每一步我看着B，所以对于x> z我看看B中是否有连接，如果不是我保留x> z，否则我用B提供的子路径填充路径x> z，这可能类似于x-> j-> h-> z; 那么我对z-> y也是这样。 每次我也会检查是否要添加循环路径。
也许我会得到一些奇怪的路径，但它可以在大多数情况下工作。 如果我用不同的“切割阈值”尝试扩展解决方案，也许我可以接近尊重K约束。
我相信你可以使用Bellman-Ford算法的修改版来解决这个问题。
Bellman-Ford基于以下动态编程循环，试图找出从某个起始节点到每个其他节点的最短路径，其长度不超过m，长度为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，然后使用上述递归和动态规划计算所有t的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难的，所以除非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变量来更新代码。
希望这可以帮助！
对于问题的新版本，汉密尔顿路径有所减少（使问题变得棘手）。 以哈密尔顿路径的实例（即一个假设其边缘具有单位权重的图形）为例，将来源和下降顶点以及权重2的边缘从源头添加到其他所有其他边缘，并从源头添加到所有其他边缘。 设置K = | V | + 2并请求从源到宿的路径。 当且仅当最佳平均边长为（| V | + 3）/（| V | + 2）时存在Hamilton路径。
谨慎地告诉我们为什么你要这些路径，以便我们可以建议你一个合理的近似策略？
您可以稍微修改Bellman-Ford算法以使用至多K个边/节点来查找最小路径。 如果边的数量是固定的，则必须将总成本降至最低，因为平均成本为TotalCost / NumberOfEdges。
其中一个解决方案是将NumberOfEdges从1到K迭代，找到最小的总成本并选择最小的TotalCost / NumberOfEdges。
链接地址: http://www.djcxy.com/p/6001.html上一篇: Route problem in a graph: minimize average edge cost instead of total cost