维比特算法

维比特算法

问题

动态规划最佳的路径:

路径总数为:

3*3*3=27

每次从头算到尾,每一条路径需要经过4次加法,共:

27*4 = 108

维比特算法的推演

假设我们处于位置t(有n个选择),如果我们想要知道t+1(m个选择)步应该怎么走,我们需要知道从(0-t)共n个路径的值(这个路径的值已经是前面的最小的了)是多少。还需要知道从t到t+1的对于n中的每一个,对应的m个选择的路径是多少。这样对于位置t上的每一个n的(0, t)已知,(t , t+1)已知,就可以通过计算得到对于t+1时刻的m个选择中的每一个,(0, t+1)的最短路径分别是什么了。

简单来讲,就是当处于t时刻时,分别独立计算t时刻,经过n个神经元中的任何一个时,该神经元的历史最小值和未来的最小值。

从A到B

现在我们在A点,因为下一步如果我们在(B1, B2, B3)点,去思考B1该往哪一个(C1, C2,C3)走时,需要知道B1之前的所有路径的最短的值。

PS : 这里会有疑惑,如果我已经到了B1,选择往(C1, C2,C3)走时,只要选择最短的一个比方说5不就行了,为什么还需要计算A-B1最短的值呢?

原因是:我们其中在在每一步时,不仅仅是做判断,很重要的是记录下路径的值,这样我们才能在最后一步的时候,把全部的值,也就是全局的值加起来,进行计算全局的最小值,也就是最短路径。

假如,我们已经选了B1-C1=5作为选择,但是还是要计算A-B1=6的

A-B1-C1 = 6+5 =11

而:A-B2 =7, B2-C2 = 3

A-B2-C2 = 7+ 3 =10

我们需要通过这种方式去进行全局的判断。

也就是说,我们每一步的选择都不是选择,而只是在为最后一步的最终判决积累数据而已。

简单来讲,如果我们已经处于t时刻(n), 我们只需要计算出t+1时刻(m),m个t+1时刻的最短路径值为下一步积累数据就好了。

在A-B的例子中:

我们在A时刻,我们需要计算B时刻,3个选择,过往的最短路径值是多少就可以了,那么经过B1, B2, B3的最短路径值为:

计算经过B1的路径:

A-B1 = 6

计算经过B2的路径:

A-B2 = 7

计算经过B3的路径:

A-B3 = 5

计算复杂度 = 3次加法

min(B1, B2, B3) = [6,7,5]

所有通过B1的路径中:A-B1是最短的,为6;

所有通过B2的路径中:A-B2是最短的,为7;

所有通过B3的路径中:A-B3是最短的,为5;

下一步计算时,与A再无关系,只基于B1、B2、B3三个出发点和(6,7,5)对应的初始值(历史值)进行计算:

B1(A-B1=6);

B2(A-B2=7);

B3(A-B3=5);

从B到C

我们在B时刻,我们需要计算C时刻,3个选择,经过C1、C2、C3的最短路径就好了:

计算经过C1的路径:

A-B1-C1 = 6+5 = 11

A-B2-C1 = 7+4 = 11

A-B3-C1 = 5+4 = 9

计算经过C2的路径:

A-B1-C2 = 6+6 = 12

A-B2-C2 = 7+3 = 10

A-B3-C2 = 5+6 = 11

计算经过C3的路径:

A-B1-C3 = 6+9 = 15

A-B2-C3 = 7+7 = 14

A-B3-C3 = 5+6 = 11

计算复杂度 = 3*3 = 9 次加法

那么C1, C2,C3的最短路径为:

min(C1, C2, C3) = [A-B3-C1=5+4=9, A-B2-C2=7+3=10, A-B3-C3=5+4=11]

所有通过C1的路径中:A-B3-C1是最短的,为9;

所有通过C2的路径中:A-B2-C2是最短的,为10;

所有通过C3的路径中:A-B3-C3是最短的,为11;

下一步计算时,与A、B再无关系,只基于C1、C2、C3三个出发点和(9,10,11)对应的初始值(历史值)进行计算:

C1(9);

C2(10);

C3(11);

从C到D

我们现在处在C时刻,需要计算D时刻,3个选择,经过D1、D2、D3的最短路径:

计算经过D1的路径:

C1-D1 = (A-B3-C1) - D1 = 9 + 7 = 16

C2-D1 = (A-B2-C2) - D1 = 10 + 5 = 15

C3-D1 = (A-B3-C3) - D1 = 11 + 5 = 16

计算经过D2的路径:

C1-D2 = (A-B3-C1) - D2 = 9 + 8 = 17

C2-D2 = (A-B2-C2) - D2 = 10 + 4 = 14

C3-D2 = (A-B3-C3) - D2 = 11 + 7 = 18

计算经过D3的路径:

C1-D3 = (A-B3-C1) - D3 = 9 + 3 = 12

C2-D3 = (A-B2-C2) - D3 = 10 + 3 = 13

C3-D3 = (A-B3-C3) - D3 = 11 + 6 = 17

计算复杂度 = 3 *3 = 9 次加法

min(D1, D2,D3) = [A-B2-C2-D1=10+5=15,A-B2-C2-D2=10+4=14, A-B3-C1-D3=9+3=12 ]

所有通过D1的路径中:A-B2-C2-D1是最短的;

所有通过D2的路径中:A-B2-C2-D2是最短的;

所有通过D3的路径中:A-B3-C1-D3是最短的;

下一步计算时,与A、B、C再无关系,只基于D1、D2、D3三个出发点和(9,10,11)对应的初始值(历史值)进行计算:

D1(15);

D2(14);

D3(12);

从D到E

现在我们处于D时刻,需要计算E时刻,1个选择:

计算经过E的路径:

D1-E = A-B2-C2-D1-E = 15 + 4 = 19

D2-E = A-B2-C2-D2-E = 14 + 8 = 22

D3-E = A-B3-C1-D3-E = 12 + 5 = 17

计算复杂度 = 3次加法

最算路径为:

min(E) = A-B3-C1-D3-E = 12+5=17

总结

计算复杂度

维比特计算复杂度 = 3+3*3+3*3+3 = 24 次加法

可以看到相对于开始的108次加法,我们只是需要24次即可。

而且在可见的未来,如果中间增加了一层,原来的遍历算法需要增加:

(3*3*3*3)4 = 108\3 = 324

基本上是每一层的个数乘以原来所有的路径

可是维比特是计算复杂度只是:

3 + 3*3 + 3*3 + 3*3 +3 = 24+9 = 33

对比一下,遍历算法的本质上叠成,而维比特算法的本质是相加.

维比特降低计算复杂度的直观理解

我们拿从C到D举例:

其中的D1 :

计算经过D1的路径:

C1-D1 = (A-B3-C1) - D1 = 9 + 7 = 16

C2-D1 = (A-B2-C2) - D1 = 10 + 5 = 15

C3-D1 = (A-B3-C3) - D1 = 11 + 5 = 16

此时我们计算C1-D1,只用了一次加法计算,但是实际上,如果真正的计算经过D1的路径有多少条呢?

3*3 = 9 条,也就是说,如果我们不把历史记录下来,每一次我们多走一步都要重新计算的话,我们每次都要指数级的计算叠层每一种可能。

而维比特相当于,把历史记录下来,并取最短的那个也记录下来,以后再计算的时候,都基于这个最短的计算,其他的都不计算了。

比如我们计算C1-D1的时候,我们只计算(A-B3-C1) - D1 = 9 + 7 = 16 的路径。

却理都不理:(A-B1-C1)-D1 = 11+7 = 18 的路径。

而且以后的,凡是经过D1的的路径,都再也理都不理(A-B1-C1)-D1 这种可能了。

因为我们已经证实,在所有C1-D1之前的经过C1的路径中,已经没有比A-B3更小的了。也就没有必要再去计算别的可能了。

可以看到通过这种方式,如果层数增加,这种算法省去掉不需要的计算步骤是非常非常非常可观的。

维比特也就通过这种基于历史和未来的一小步的方法,使得在全局范围可控并全局最优,且计算量可以接受。