Dynamic Programming Using Typeless Graphs:

We will now use our typeless graph class developed in to implement a standard dynamic programming algorithm. The standard Dynamic Programming algorithm is an iterative technique for minimizing the cost of moving from a chosen start to a chosen goal node in a graph of N nodes. If we label all of the nodes in the graph with say the lexicographic ordering, 0 q  $\leq$  N, the standard Dynamic Programming algorithm may be stated as follows: if J_q denotes the cost of moving from node q to the goal, then the optimal node costs satisfy the equation:

$$\inf_{i \in S(q)}^{} \rightarrow$$ J_q =

where S(q) is the set of successors to a given node and T_q $\rightarrow$ i denotes the cost of moving from node q to the successor node i $\in$ S(q). This equation is usually solved via an iterative procedure:

$$\inf_{i \in S(q)}^{} \rightarrow$$ J_q^{t + 1} =

with the initial goal costs J_q set in some fashion.