**.
我试图找到从u到v的最短路径的长度(边长的最小总和),还有2个额外的限制：
>路径包含的蓝色边数与红色边数相同.
>路径包含的黑边数不大于p.
我想出了一个指数时间算法,我觉得它可行.它遍历所有长度为n-1的二进制组合,它们表示从u开始的路径,方式如下：
> 0是蓝色边缘
> 1是红色边缘
>无论什么时候都有黑边
>组合从1开始.第一个边缘(来自u)然后是左边的第一个黑色边缘.
>组合以0结束.然后最后一个边缘(到v)则是右边的最后一个黑色边缘.
>相邻的数字是不同的.这意味着我们从蓝色边缘变为红色边缘(反之亦然),因此中间有一个黑色边缘.
该算法将忽略不符合前面提到的2个要求的路径,并计算那些路径的长度,然后找到最短的路径.然而,这样做可能会非常慢,我正在寻找一些提示,以提出更快的算法.我怀疑用动态编程可以实现,但我真的不知道从哪里开始.任何帮助将非常感激.谢谢.
解决方法
为了理解我的答案,首先要理解一个原始的N ^ 3答案:(我无法弄清楚我的实际答案是否比粗N ^ 3更好,但它的平均情况要好得多).
注意N必须是奇数,表示为N = 2H 1.(P也必须是奇数.如果给定偶数P,则减去P.但如果N是偶数,则拒绝输入.)
使用3个实际坐标和一个隐含坐标存储成本：
J =第0列到第N列
R =红色边缘0到H的计数
B =黑色边缘0到P的计数
S =边奇数或偶数(S仅为B％1)
我们将计算/存储成本[J] [R] [B]作为使用正好R红色边缘和B黑色边缘到达列J的最低成本方式. (我们也使用了J-R蓝色边缘,但这个事实是多余的).
为方便起见直接写入成本,但通过访问器c(j,r,b)读取它,当r <0 ||时返回BIG b <0,否则返回成本[j] [r] [b]. 那么最里面的一步就是：
If (S) cost[J+1][R][B] = red[J]+min( c(J,R-1,B),c(J,B-1)+black[J] ); else cost[J+1][R][B] = blue[J]+min( 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的成本,则新成本是无用数据.如果结构的最后一个dim是map而不是array,我们可以很容易地计算出从存储空间和时间中删除无用数据的序列.但是,减少的时间乘以那些地图的平均大小(最多为P)的对数.所以平均情况下可能是一场胜利,但最糟糕的情况可能是亏损. 稍微考虑一下成本所需的数据类型和BIG所需的值.如果该数据类型中的某些精确值既与最长路径一样大又小到可以存储在该数据类型中的最大值的一半,那么这对于BIG来说是一个微不足道的选择.否则,您需要更仔细的选择以避免任何舍入或截断. 如果你遵循这一切,你可能会理解我认为难以解释的更好的方法之一：这将使元素大小加倍,但将元素数量减少到不到一半.它将std :: map调整的所有好处发送到基本设计而没有log(P)成本.它会缩短平均时间,不会伤害病理时间. 定义包含成本和黑计数的结构CB.主存储器是矢量< vector< CB>.外部向量对于每个有效的J,R组合具有一个位置.这些是规则模式,因此我们可以很容易地计算给定J,R或给定位置的J,R的向量中的位置.但是保持这些增量更快,因此J和R是隐含的而不是直接使用.矢量应保留为其最终大小,约为N ^ 2/4.如果您预先计算H,0的索引可能是最好的
每个内部载体在严格增加的B序列中具有C,B对,并且在每个S内,严格降低C序列.内部向量一次生成一个(在临时向量中),然后复制到它们的最终位置,之后只读取(未修改).在每个内部矢量的生成内,候选C,B对将以增加的B序列生成.因此,在构建临时向量时,保持bestOdd和bestEven的位置.然后,只有当C的C值低于最佳值(或者最佳值尚不存在)时,才将每个候选者推入向量.我们也可以将所有B< P J-N视为B == S,因此该范围内的较低C代替而不是推动. 外部向量的隐含(从未存储)J,R对以(0,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处存在到J列的路径,使用正好R红色分支和B黑色分支并且不存在存在一条到J列的路径,它使用正好的R红色分支和相同的S,其中C’或B’中的一个更好而另一个不差.
