ABSTRACT
Problems occurring in finance, simple change-making, or TV game shows can all be viewed as sequential decision-making problems. Such situations typically involve a number of stages, each composed of states. A decision at a given state leads us to a state in the next stage, which again requires a decision. We can represent these decision problems using both tables and graphs. We first discuss a greedy approach, which successively takes the best option at each stage to obtain an answer. While quick, it need not produce the best (or optimal) overall solution. We then explore the technique of dynamic programming, which breaks up a formidable decision problem into several smaller subproblems. By using a “best of the best” approach (incorporating the best solution to each subproblem), we can then optimally solve the original problem. Heuristic algorithms such as the greedy approach are useful if we are interested in quickly obtaining a good, though not necessarily optimal, answer.
