c – 在图表中查找最短路径,并附加其他限制

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

为了理解我的答案,首先要理解一个原始的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’中的一个更好而另一个不差.