在有额外限制的情况下查找图中的最短路径
Finding shortest path in a graph, with additional restrictions
我有一个包含 2n 个顶点的图，其中每条边都有定义的长度。看起来像 **
**.
我试图找到从 u 到 v 的最短路径的长度（边长的最小总和），其中2 个附加限制：
- 路径包含的蓝色边数与红色边数相同。
- 路径包含的黑边数不大于p。
我想出了一个我认为可行的指数时间算法。它以下列方式遍历所有长度为 n - 1 的二进制组合，表示从 u 开始的路径：
- 0是蓝边
- 1是红边
- 每当有黑边
- 组合以1开头。第一条边（来自 u）就是左边的第一个黑色边。
- 组合以0结尾。然后最后一条边（到 v）就是右边最后一个黑色的边。
- 相邻数字不同。这意味着我们从蓝色边缘变为红色边缘（反之亦然），因此中间有一个黑色边缘。
该算法会忽略不满足前面提到的 2 个要求的路径，并计算满足的路径的长度，然后找到最短的路径。然而，这样做可能会非常慢，我正在寻找一些技巧来提出更快的算法。我怀疑可以通过动态编程来实现，但我真的不知道从哪里开始。任何帮助将不胜感激。谢谢
我觉得 Dynamic Programming 有问题。
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 - 当前节点
- i - #reds_traversed - #blues_traversed
- k - #black_edges_left
停止子句在目标节点，到达就结束，只允许i=0到达，k<=p
递归调用正在检查每个点 "what is better? going through black or going though red/blue"，并从两个选项中选择最佳解决方案。
思路是，D(v,i,k)是从v到目标（t）的最优结果，#reds-#blues使用的是i，您最多可以使用 k 个黑边。
由此，我们可以得出结论D(s,0,p)是从源头到达目标的最优结果。
因为 |i| <= n, k<=p<=n - 该算法的总 运行 时间是 O(n^3)，假设在动态规划中实现。
您的指数算法本质上是一个深度优先搜索树，您可以在下降时跟踪成本。
您可以通过跟踪目前为止看到的最佳解决方案并 p运行ing 任何超出目前最佳解决方案的分支来使其分支定界。
或者，您可以将其设为广度优先搜索，按成本排序，这样一找到任何解决方案，它就会名列前茅。
我过去这样做的方法是深度优先，但有 预算。
我 p运行e 任何超出预算的分支机构。
然后我 运行 如果预算为 0。
如果它没有找到任何解决方案，我 运行 它的预算为 1。
我不断增加预算，直到找到解决方案。
这可能看起来像很多重复，但由于每个 运行 访问的节点比前一个多得多，因此前面的 运行 并不重要。
这是解决方案成本的指数，而不是网络规模。
编辑：不知何故，我查看了问题中的 "Finding shortest path" 短语并忽略了 "length of" 短语，原始问题后来澄清了意图。因此，我下面的两个答案都存储了大量额外数据，以便在计算出长度后轻松回溯正确的路径。如果您不需要在计算长度后回溯，我的粗略版本可以将其第一个维度从 N 更改为 2，并且只存储一个奇数 J 和一个偶数 J，覆盖旧的任何内容。我的更快版本可以降低管理 J、R 交互的所有复杂性，并且还可以将其外部级别存储为 [0..1][0..H] None ，这会大大改变时间，但也会大大改变存储空间。
要理解我的答案，首先要理解一个粗略的 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）
我们将 compute/store 成本 [J][R][B] 作为到达 J 列的成本最低的方法，正好使用 R 条红色边缘和 B 条黑色边缘。 （我们也使用了 J-R 蓝色边缘，但这个事实是多余的）。
为了方便直接写入 cost 但通过访问器 c(j,r,b) 读取它 returns BIG when r<0 || b<0 and returns 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] );
将成本[0][0][0]初始化为零，对于超粗版本，将所有其他成本[0][R][B]初始化为大。
您可以非常粗略地循环遍历递增的 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的成本，则该新成本是无用数据。如果结构的最后一个 dim 是映射而不是数组，我们可以很容易地计算一个序列，从存储 space 和时间中删除无用的数据。但是减少的时间然后乘以这些地图的平均大小（最大 P）的对数。所以在平均情况下可能会赢，但在最坏的情况下可能会输。
考虑一下cost需要的数据类型和BIG需要的值。如果该数据类型中的某个精确值既与最长路径一样大，又与可存储在该数据类型中的最大值的一半一样小，那么这对于 BIG 来说是一个微不足道的选择。否则你需要更谨慎的选择以避免任何舍入或截断。
如果您遵循了所有这些，您可能会理解我认为难以解释的更好方法之一：这将使元素大小增加一倍，但将元素数量减少到不到一半。它将获得 std::map 对基本设计进行调整的所有好处，而无需 log(P) 成本。它会在不损害病理病例时间的情况下大大缩短平均时间。
定义一个包含成本和黑色计数的结构 CB。主存储是一个vector<vector<CB>>。每个有效的 J,R 组合都有一个外部向量的位置。这些都是有规律的模式，所以我们可以很容易地计算给定 J、R 或给定位置的 J、R 在向量中的位置。但是以增量方式保留它们会更快，因此 J 和 R 是隐含的而不是直接使用。该向量应保留其最终大小，约为 N^2/4。最好预先计算 H,0
的索引
每个内部向量在每个 S 中严格递增 B 序列 和 中都有 C,B 对，严格递减 C 序列。内部向量一次生成一个（在临时向量中），然后复制到它们的最终位置，之后只读取（不修改）。在每个内部向量的生成过程中，候选 C,B 对将以递增的 B 序列生成。因此，在构建临时向量时保持 bestOdd 和 bestEven 的位置。然后，只有当每个候选的 C 低于最佳（或最佳尚不存在）时，它才会被推入向量中。我们还可以将所有 B<P+J-N 视为 B==S，因此该范围内的较低 C 会替换而不是推入。
外向量的隐含（从未存储）J,R 对以 (0,0) (1,0) (1,1) (2,0) 开始并以 (N-1,H) 结束-1) (N-1,H) (N,H)。增量地使用这些索引是最快的，因此当我们计算隐含位置 J,R 的向量时，我们将 V 作为 J,R 的实际位置，U 作为实际位置J-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 列的路径 和 不存在使用恰好 R 红色分支和相同 S 的 J 列路径，其中 C' 或 B' 之一更好，另一个不会更糟。
我有一个包含 2n 个顶点的图，其中每条边都有定义的长度。看起来像 **
**.
我试图找到从 u 到 v 的最短路径的长度（边长的最小总和），其中2 个附加限制：
- 路径包含的蓝色边数与红色边数相同。
- 路径包含的黑边数不大于p。
我想出了一个我认为可行的指数时间算法。它以下列方式遍历所有长度为 n - 1 的二进制组合，表示从 u 开始的路径：
- 0是蓝边
- 1是红边
- 每当有黑边
- 组合以1开头。第一条边（来自 u）就是左边的第一个黑色边。
- 组合以0结尾。然后最后一条边（到 v）就是右边最后一个黑色的边。
- 相邻数字不同。这意味着我们从蓝色边缘变为红色边缘（反之亦然），因此中间有一个黑色边缘。
该算法会忽略不满足前面提到的 2 个要求的路径，并计算满足的路径的长度，然后找到最短的路径。然而，这样做可能会非常慢，我正在寻找一些技巧来提出更快的算法。我怀疑可以通过动态编程来实现，但我真的不知道从哪里开始。任何帮助将不胜感激。谢谢
我觉得 Dynamic Programming 有问题。
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 - 当前节点
- i - #reds_traversed - #blues_traversed
- k - #black_edges_left
停止子句在目标节点，到达就结束，只允许i=0到达，k<=p
递归调用正在检查每个点 "what is better? going through black or going though red/blue"，并从两个选项中选择最佳解决方案。
思路是，D(v,i,k)是从v到目标（t）的最优结果，#reds-#blues使用的是i，您最多可以使用 k 个黑边。
由此，我们可以得出结论D(s,0,p)是从源头到达目标的最优结果。
因为 |i| <= n, k<=p<=n - 该算法的总 运行 时间是 O(n^3)，假设在动态规划中实现。
您的指数算法本质上是一个深度优先搜索树，您可以在下降时跟踪成本。
您可以通过跟踪目前为止看到的最佳解决方案并 p运行ing 任何超出目前最佳解决方案的分支来使其分支定界。
或者，您可以将其设为广度优先搜索，按成本排序，这样一找到任何解决方案，它就会名列前茅。
我过去这样做的方法是深度优先，但有 预算。 我 p运行e 任何超出预算的分支机构。 然后我 运行 如果预算为 0。 如果它没有找到任何解决方案，我 运行 它的预算为 1。 我不断增加预算，直到找到解决方案。 这可能看起来像很多重复，但由于每个 运行 访问的节点比前一个多得多，因此前面的 运行 并不重要。
这是解决方案成本的指数，而不是网络规模。
编辑：不知何故，我查看了问题中的 "Finding shortest path" 短语并忽略了 "length of" 短语，原始问题后来澄清了意图。因此，我下面的两个答案都存储了大量额外数据，以便在计算出长度后轻松回溯正确的路径。如果您不需要在计算长度后回溯，我的粗略版本可以将其第一个维度从 N 更改为 2，并且只存储一个奇数 J 和一个偶数 J，覆盖旧的任何内容。我的更快版本可以降低管理 J、R 交互的所有复杂性，并且还可以将其外部级别存储为 [0..1][0..H] None ，这会大大改变时间，但也会大大改变存储空间。
要理解我的答案，首先要理解一个粗略的 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）
我们将 compute/store 成本 [J][R][B] 作为到达 J 列的成本最低的方法，正好使用 R 条红色边缘和 B 条黑色边缘。 （我们也使用了 J-R 蓝色边缘，但这个事实是多余的）。
为了方便直接写入 cost 但通过访问器 c(j,r,b) 读取它 returns BIG when r<0 || b<0 and returns 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] );
将成本[0][0][0]初始化为零，对于超粗版本，将所有其他成本[0][R][B]初始化为大。
您可以非常粗略地循环遍历递增的 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的成本，则该新成本是无用数据。如果结构的最后一个 dim 是映射而不是数组，我们可以很容易地计算一个序列，从存储 space 和时间中删除无用的数据。但是减少的时间然后乘以这些地图的平均大小（最大 P）的对数。所以在平均情况下可能会赢，但在最坏的情况下可能会输。
考虑一下cost需要的数据类型和BIG需要的值。如果该数据类型中的某个精确值既与最长路径一样大，又与可存储在该数据类型中的最大值的一半一样小，那么这对于 BIG 来说是一个微不足道的选择。否则你需要更谨慎的选择以避免任何舍入或截断。
如果您遵循了所有这些，您可能会理解我认为难以解释的更好方法之一：这将使元素大小增加一倍，但将元素数量减少到不到一半。它将获得 std::map 对基本设计进行调整的所有好处，而无需 log(P) 成本。它会在不损害病理病例时间的情况下大大缩短平均时间。
定义一个包含成本和黑色计数的结构 CB。主存储是一个vector<vector<CB>>。每个有效的 J,R 组合都有一个外部向量的位置。这些都是有规律的模式，所以我们可以很容易地计算给定 J、R 或给定位置的 J、R 在向量中的位置。但是以增量方式保留它们会更快，因此 J 和 R 是隐含的而不是直接使用。该向量应保留其最终大小，约为 N^2/4。最好预先计算 H,0
每个内部向量在每个 S 中严格递增 B 序列 和 中都有 C,B 对，严格递减 C 序列。内部向量一次生成一个（在临时向量中），然后复制到它们的最终位置，之后只读取（不修改）。在每个内部向量的生成过程中，候选 C,B 对将以递增的 B 序列生成。因此，在构建临时向量时保持 bestOdd 和 bestEven 的位置。然后，只有当每个候选的 C 低于最佳（或最佳尚不存在）时，它才会被推入向量中。我们还可以将所有 B<P+J-N 视为 B==S，因此该范围内的较低 C 会替换而不是推入。
外向量的隐含（从未存储）J,R 对以 (0,0) (1,0) (1,1) (2,0) 开始并以 (N-1,H) 结束-1) (N-1,H) (N,H)。增量地使用这些索引是最快的，因此当我们计算隐含位置 J,R 的向量时，我们将 V 作为 J,R 的实际位置，U 作为实际位置J-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 列的路径 和 不存在使用恰好 R 红色分支和相同 S 的 J 列路径，其中 C' 或 B' 之一更好，另一个不会更糟。