c – 在图表中查找最短路径,并附加其他限制
我有一个带有2n个顶点的图形,其中每个边都有一个定义的长度.看起来像 **
**. 我试图找到从u到v的最短路径的长度(边长的最小总和),还有2个额外的限制: >路径包含的蓝色边数与红色边数相同. 我想出了一个指数时间算法,我觉得它可行.它遍历所有长度为n-1的二进制组合,它们表示从u开始的路径,方式如下: > 0是蓝色边缘 >组合从1开始.第一个边缘(来自u)然后是左边的第一个黑色边缘. 该算法将忽略不符合前面提到的2个要求的路径,并计算那些路径的长度,然后找到最短的路径.然而,这样做可能会非常慢,我正在寻找一些提示,以提出更快的算法.我怀疑用动态编程可以实现,但我真的不知道从哪里开始.任何帮助将非常感激.谢谢. 解决方法
编辑:不知何故,我查看了问题中的“寻找最短路径”短语,并忽略了原始问题后来澄清意图的“长度”短语.因此,我的下面的答案都存储了大量额外数据,以便在计算完长度后轻松回溯正确的路径.如果您在计算长度后不需要回溯,我的原始版本可以将其第一个维度从N更改为2,只存储一个奇数J和一个偶数J,覆盖任何旧的.我的更快版本可以降低管理J,R交互的所有复杂性,也只是将其外部级别存储为[0..1] [0..H]这些都不会改变时间,但它会大大改变存储.
为了理解我的答案,首先要理解一个原始的N ^ 3答案:(我无法弄清楚我的实际答案是否比粗N ^ 3更好,但它的平均情况要好得多). 注意N必须是奇数,表示为N = 2H 1.(P也必须是奇数.如果给定偶数P,则减去P.但如果N是偶数,则拒绝输入.) 使用3个实际坐标和一个隐含坐标存储成本: 我们将计算/存储成本[J] [R] [B]作为使用正好R红色边缘和B黑色边缘到达列J的最低成本方式. (我们也使用了J-R蓝色边缘,但这个事实是多余的). 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. 最后,我们可以找到答案: 但是一半的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的第一个位置,? 内部循环使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’中的一个更好而另一个不差. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |