Source Code for Module gmisclib.dyn_prog

 1  """Viterbi search""" 
 2   
 3  import numpy 
 4   
 5   
 6   
 7   
 8 -def path(nodecost, linkcost): 
 9          # nodecost[t,j]  at time t, pitch=j 
10          # linkcosts[j1, j2]   cost to go from (t,j1) to (t+1,j2) 
11          #    where j=pitch 
12   
13          T = nodecost.shape[0] 
14          N = nodecost.shape[1] 
15   
16   
17   
18          cost = numpy.zeros((N,)) 
19   
20          bestpathto = [] 
21          for j in range(N): 
22                  bestpathto.append([j]) 
23                  cost[j] = nodecost[0,j] 
24   
25          for t in range(1,T): 
26                  nbp = [] 
27                  ncost = numpy.zeros((N,)) 
28                  for j in range(N): 
29                          cc = cost + linkcost[:,j] 
30                          assert len(cc.shape)==1 
31                          o = numpy.argmin(cc) 
32                          ncost[j] = cc[o] + nodecost[t,j] 
33                          nbp.append(bestpathto[o] + [j]) 
34                  bestpathto = nbp 
35                  cost = ncost 
36   
37          assert len(cost.shape)==1 
38          jj = numpy.argmin(cost) 
39   
40          return (cost[jj], bestpathto[jj]) 
41   
42   
43   
44 -def test1(): 
45          T = 10 
46          N = 7 
47          noc = numpy.zeros((T,N)) + 5 
48          noc[:,3] = 1 
49          linkc = numpy.zeros((N,N)) + 2 
50   
51          c, p = path(noc, linkc) 
52          assert abs(c - (10*1 + 9*2)) < 0.0001 
53          assert p == [3]*T 
54   
55 -def test2(): 
56          T = 10 
57          N = 7 
58          noc = numpy.zeros((T,N)) + 5 
59          for i in range(T): 
60                  noc[i,i%N] = 1 
61          linkc = numpy.zeros((N,N)) + 2 
62   
63          c, p = path(noc, linkc) 
64          assert abs(c - (10*1 + 9*2)) < 0.0001 
65          assert p == [0,1,2,3,4,5,6,0,1,2] 
66   
67   
68 -def test3(): 
69          T = 10 
70          N = 7 
71          noc = numpy.zeros((T,N)) + 1 
72          noc[0,0] = 0 
73          linkc = numpy.zeros((N,N)) + 2 
74          for i in range(N): 
75                  linkc[i,(i+1)%N] = 1 
76   
77          c, p = path(noc, linkc) 
78          assert abs(c - (0+9*1 + 9*1)) < 0.0001 
79          assert p == [0,1,2,3,4,5,6,0,1,2] 
80   
81  if __name__ == '__main__': 
82          test1() 
83          test2() 
84          test3() 
85