This brings to mind the Viterbi algorithm that calculates the most likely sequence of events in a hidden Markov model (Markov model itself is just a state machine on a graph with weighed edges, where each weight on a state transition is represented as a probability of that transition).<p>It's essentially bases to the same algorithm: you can eliminate sequences if they lead to the same event that is already part of a solution, but with lesser probability. The amount of paths would be exponential, but the ability to eliminate them keeps it polynomial. That really brings forth the beauty of dynamic programming.