2. General Dynamic Programming Paradigm
Society for Industrial and Applied Mathematics eBooks · 2001
We wish to introduce the General Dynamic Programming Paradigm (GDPP) in a notational form sufficiently flexible for the variety of optimization tasks surveyed in the remaining chapters of this monograph. Thus, it is convenient to have a preliminary example of how a simply stated (and also well-known) optimization task can be solved by DP. The elements introduced for its solution can then be used to give concrete referents for the more general notational system of the GDPP explicated in Section 2.2. We thus begin by giving a DP solution to the linear assignment problem. 2.1 An Introductory Example: Linear Assignment The linear assignment (LA) task (in one of its simple variants) can be phrased using two object sets, where each contains n members, say, U = {u1, …, un} and V = {v1,…, vn}, and an n × n merit matrix C = {cij}, where cij denotes the value of pairing objects ui and vj. The optimization task is to find a one-to-one matching of the objects in U and V that will maximize the sum of the n merit values produced by the matching. Interpretively, the objects in U might represent n people who must be allocated to the n tasks denoted by the objects in V, where cij is the value of assigning task vj to person ui. A complete enumeration strategy for the LA task requires the evaluation of the sum of merit values for all n! one-to-one matchings of the objects in U and V.