L notation
----------

In the programs and here, I use 'el' instead of 'l' to represent a
lowercase L because 'l' by itself looks too much like the number '1'.


Value of L vs. el'th best-paths
-------------------------------

For a normal non-Kalman cost function, the results produced by the L-list
Viterbi algorithm are the globally optimum L best solutions.  Given two
values of L, L1 and L2 with L1<L2, The L1-best solutions produced using
L=L1 will be the same as the first L1-best solutions produced using L=L2.
Using a larger value of L does not affect the lower el'th solutions.

For example, comparing L1=2 with L2=3, there is no way for some choice
which represents the 3rd-best at some point to become the 2nd best at a
latter point.  If, at some point, the three best choices at some state have
costs [1, 2, 3], in the transition to the next state some fixed cost, say
x, will be added onto each of them yielding [1+x, 2+x, 3+x].  So there is
no way for the 3 to beat out the 2.

However, when using a Kalman cost function, the above is not true.
Using the above example, with the three best choices having costs
[1, 2, 3] at some state, in the transition to the next state
_different_ incremental costs, say [a, b, c], will be added to
them yielding [1+a, 2+b, 3+c].  In this case, it is possible for
3+c to be less than 2+b.  This is because each choice represents
a different Kalman filter, and the incremental costs in a state
transition depend on the filters, not just the state indices.

In the Kalman-cost case, even the best single path depends on the value
of L.  This means that no path pruning can be done if one wants the
global optimum, and thus the L-list Viterbi algorithm does not
necessarily produce the L-best paths.

Following is a small example, implemented in file x11.m, illustrating
the last point.

There are 6 measurements, 2 for each time unit:

	i       x  y  xv yv
	
	1	0  1  2  0
	2	0  3  0 -3
	
	3	1  2  0  0
	4	10 10 0  0
	
	5	1  0  0  0
	6	10 10 0  0

Using Viterbi with the Kalman cost function and K=L=1, the best path comes
out as:
					cost
       i =  1       3       5		4.88

Using L=2 produces paths:
					cost
       i =  2       3       5		3.22 	-- best
            1       3       5		4.88	-- 2nd best

The best path produced using L=2 is different from the path produced
using L=1, and has lower cost.