查找图表中的最短路径,还有其他限制

Question

我有一个带有2n个顶点的图形,其中每个边都有一个定义的长度.看起来像**

**.

我试图找到从u到v的最短路径的长度(边长的最小总和),还有2个额外的限制:

• 路径包含的蓝色边数与红色边数相同.
• 路径包含的黑边数不大于p.

我想出了一个指数时间算法,我觉得它可行.它遍历所有长度为n-1的二进制组合,它们表示从u开始的路径,方式如下:

• 0是蓝色边缘
• 1是红色边缘
• 每当有黑边
  • 组合从1开始.然后第一个边缘(来自u)是左边的第一个黑色边缘.
  • 组合以0结尾.然后最后一个边缘(到v)是右边的最后一个黑色边缘.
  • 相邻的数字是不同的.这意味着我们从蓝色边缘变为红色边缘(反之亦然),因此中间有一个黑色边缘.

该算法将忽略不符合前面提到的2个要求的路径,并计算那些路径的长度,然后找到最短的路径.然而,这样做可能会非常慢,我正在寻找一些提示,以提出更快的算法.我怀疑用动态编程可以实现,但我真的不知道从哪里开始.任何帮助将非常感激.谢谢.

Answer 1

对我来说似乎是动态编程问题.

In here, v,u are arbitrary nodes.
Source node: s
Target node: t

For a node v, such that its outgoing edges are (v,u1) [red/blue], (v,u2) [black].
D(v,i,k) = min { ((v,u1) is red ? D(u1,i+1,k) : D(u1,i-1,k)) + w(v,u1) ,
                  D(u2,i,k-1) + w(v,u2) }
D(t,0,k) = 0           k <= p
D(v,i,k) = infinity    k > p //note, for any v
D(t,i,k) = infinity    i != 0

说明:

• v - 当前节点
• 我 - #reds_traversed - #blues_traversed
• k - #black_edges_left

stop子句在目标节点处,在到达目标节点时结束,并且仅在i = 0时允许到达它,并且k <= p

递归调用是在每个点检查"什么是更好的？通过黑色或通过红色/蓝色",并从两个选项中选择最佳解决方案.

这个想法是,D(v,i,k)从使用v到目标(t)的最佳结果#reds-#blues是 i,你可以使用最多的k黑色边缘.
由此,我们可以得出结论D(s,0,p)是从源头到达目标的最佳结果.

因为|i| <= n, k<=p<=n- O(n^3)假设在动态编程中实现,算法的总运行时间.

Answer 2

编辑：不知何故，我查看了问题中的“寻找最短路径”短语，并忽略了“长度”短语，其中原始问题后来澄清了意图。因此，我下面的两个答案都存储了大量额外的数据，以便在计算出路径长度后轻松回溯正确的路径。如果计算长度后不需要回溯，我的粗略版本可以将其第一个维度从 N 更改为 2，并仅存储一个奇数 J 和一个偶数 J，覆盖任何较旧的内容。我的更快版本可以降低管理 J、R 交互的所有复杂性，并且只存储其外部级别，因为[0..1][0..H] 这些都不会改变时间太多，但它会改变存储很多。

要理解我的答案，首先要理解一个粗略的 N^3 答案：（我无法弄清楚我的实际答案是否比粗略的 N^3 有更好的最坏情况，但它有更好的平均情况）。

注意N必须是奇数，表示为N=2H+1。（P 也必须是奇数。如果给定偶数 P，则只需递减 P。但如果 N 为偶数，则拒绝输入。）

使用 3 个实坐标和 1 个隐含坐标存储成本：
J = 列 0 到 N
R = 红边计数 0 到 H
B = 黑边计数 0 到 P
S = 奇数或偶数边（S 只是B%1）

我们将计算/存储成本[J][R][B]，作为使用恰好R个红色边缘和恰好B个黑色边缘到达J列的最低成本方式。（我们也使用了 JR 蓝边，但这个事实是多余的）。
为了方便起见，直接写入cost但通过访问器 c(j,r,b) 读取它，当该访问器返回 BIG 时返回 BIG r<0 || b<0，否则返回 cost[j][r][b]。

那么最里面的步骤就是：

If (S)
   cost[J+1][R][B] = red[J]+min( c(J,R-1,B), c(J,R-1,B-1)+black[J] );
else
   cost[J+1][R][B] = blue[J]+min( c(J,R,B), c(J,R,B-1)+black[J] );

将 cost[0][0][0] 初始化为零，对于超级粗略版本，将所有其他 cost[0][R][B] 初始化为 BIG。
您可以非常粗略地循环遍历递增的 J 序列以及您喜欢计算所有这些的任何 R、B 序列。

最后我们可以找到答案： min( min(cost[N][H][all odd]), black[N]+min(cost[N][H][all even]) )

但一半的 R 值并不是真正的问题。上半场任何事情R>J都是不可能的，下半场任何事情R<J+H-N都是无用的。您可以轻松地避免计算这些。使用稍微智能的访问器函数，您可以避免在需要计算的边界情况下使用从未计算过的位置。

如果任何新成本[J][R][B]不小于相同J、R和S但较低B的成本，则该新成本是无用数据。如果结构的最后一个暗淡是映射而不是数组，我们可以轻松地按顺序进行计算，从存储空间和时间中删除无用的数据。但是，减少的时间会乘以这些地图的平均大小（最多 P）的对数。因此，在平均情况下可能会获胜，但在最坏的情况下可能会失败。

稍微考虑一下成本所需的数据类型和 BIG 所需的值。如果该数据类型中的某个精确值既与最长路径一样大，又与该数据类型中可以存储的最大值的一半一样小，那么这对于 BIG 来说是一个简单的选择。否则，您需要更仔细的选择以避免任何舍入或截断。

如果您遵循了所有这些，您可能会理解我认为很难解释的更好方法之一：这将使元素大小加倍，但将元素数量减少到一半以下。它将获得 std::map 调整到基本设计的所有好处，而无需 log(P) 成本。它将大大缩短平均时间，而不会影响病理病例的时间。

定义一个包含成本和黑色计数的 CB 结构体。主要存储是一个vector<vector<CB>>. 对于每个有效的 J,R 组合，外向量都有一个位置。它们具有规则的模式，因此我们可以轻松计算给定 J,R 的向量中的位置或给定位置的 J,R。但增量保留这些速度会更快，因此 J 和 R 是隐含的而不是直接使用。向量应保留其最终大小，约为 N^2/4。如果您预先计算索引可能是最好的H,0

每个内部向量在严格递增的 B 序列中具有 C、B 对，并且在每个 S 内具有严格递减的 C 序列。内部向量一次生成一个（在临时向量中），然后复制到其最终位置，之后仅读取（不修改）。在生成每个内部向量时，将以递增的 B 序列生成候选 C、B 对。因此，在构建临时向量时保持 bestOdd 和 bestEven 的位置。然后，仅当每个候选者的 C 低于最佳值（或者最佳值尚不存在）时，才会将其推入向量。我们还可以将所有视为B<P+J-NB==S，因此该范围内较低的 C 会替换而不是推送。

外部向量的隐含（从未存储）J,R 对以 (0,0) (1,0) (1,1) (2,0) 开头，以 (N-1,H-1) (N -1，H）（N，H）。增量地使用这些索引是最快的，因此当我们计算隐含位置 J,R 的向量时，我们将VJ,R 的实际位置以及UJ-1,R 和 minU 的实际位置作为J-1的第一个位置，？和 minV 作为 J 的第一个位置，？和minW作为J+1的第一个位置，？
在外循环中，我们将 minV 复制到 minU，将 minW 复制到 minV 和 V，并且很容易计算新的 minW 并决定 U 是从 minU 还是 minU+1 开始。

内部循环将 V 推进到（但不包括）minW，同时每次 V 推进时推进 U，并且在典型位置中使用位置 U-1 处的向量和位置 U 处的向量一起计算位置 V 的向量但您必须涵盖 U==minU 的特殊情况（其中不使用 U-1 处的向量）和 U==minV 的特殊情况（其中仅使用 U-1 处的向量）。

组合两个向量时，您可以按 B 值同步遍历它们，使用其中一个或另一个根据您遇到的 B 值生成候选向量（见上文）。

概念：假设您了解如何存储具有隐含 J,R 和显式 C,B 的值：其含义是，存在一条以成本 C 使用恰好 R 红色分支和恰好 B 黑色分支到列 J 的路径，并且不存在存在一条通向 J 列的路径，该路径恰好使用 R 个红色分支和相同的 S，其中C'或 之一B'更好，而另一个不更差。