[frames] | no frames]

# Source Code for Module gmisclib.dyn_prog

``` 1  """Viterbi search"""
2
3  import numpy
4
5
6
7
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):
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
<!--
expandto(location.href);
// -->

```

 Generated by Epydoc 3.0.1 on Thu Sep 22 04:25:13 2011 http://epydoc.sourceforge.net