bellman
Dynamic programming algorithm for optimization of sequential processes.
(route, mincost)=bellman(cost)
Inputs
costs : A list of matrices, i.e. costs = {C1,C2,C3,...Cn} where C1, C2,... are matrices as defined below.
Outputs
route : The optimal route as defined below.
mincost : The minimal cost associated with the optimal route.


Description
The inputs define the problem as follows: (a) a process with n+1 stages, (b) associated with each stage i there are m[i] states (with m[1] = m[n+1] = 1 ) , (c) for each stage a cost matrix Ci of dimension m[i] by m[i+1] such that Ci[p,q] is the cost of the transition from the state p at stage i to the state q at stage i+1 , and (d) for each stage i , the states are numbered sequentially from 1 to m[i] .

A route is a vector R of size n+1 , with R[i] being the state to be selected at stage i (with R[1] = R[n+1] = 1 ). The problem, succinctly stated, is to find a route R such that the total cost
    C1[1,R[2]] + C2[R[2],R[3]] + C3[R[3],R[4]] + ...
     ... + Cn[R[n],1]
is minimized.

In the example given below, the stages are the regions (defined by a group of cities) of the country, the states are the cities in the regions, the elements of the cost matrices are the distances from the cities in one region to the cities in the next, and the total cost is the the total distance traveled from the first region to the last with the constraints that (a) one and only one city in each region must be in the route, and (b) the regions must be visited in the specified order.

Note the curse of dimensionality associated with dynamic programming problems: this function can be used only for relativeley small problems. (A measure of the size of the problem is the product of the number of columns in each of the matrices Ci , as this is the number of possible routes of which the optimal one is to be found.)


Example
>>/* We solve the problem of finding the optimal route for
>   going from Sacramento to New York City through
>   three regions visiting at least one city in each region.
>*/
>>// Distance matrix for traveling from [Sacramento] to [Boise, Elko, Las Vegas]
>>// (In a distance matrix rows correspond to city of origin
>>//  and columns to destinations.)
>>cities{1}={"Scaramento"}
>>cities{2}={"Boise", "Elko", "Las Vegas"};
>>c1=[554 442 563];
>>// Distance matrix for traveling from [Boise, Elko, Las Vegas] 
>>// to [Bismarck, Omaha, Dallas]
>>cities{3}={"Bismarck", "Omaha", "Dallas"} 
>>c2=[1091 1230 1699
>     1134 1162 1632
>     1143 1284 1220] 
>>// Distance matrix for traveling from [Bismarck, Omaha, Dallas] 
>>// to                   [Madison, St. Louis, Memphis, Indianapolis]
>>cities{4}={"Madison", "St. Louis", "Memphis", "Indianapolis"}
>>c3=[694  1037  1304 1018
>     429  433    701  608
>     1007  650   450  899];
>>// Distance matrix for traveling from
>>// [Madison, St. Louis, Memphis, Indianapolis]
>>// to New York City
>>cities{5}={"New York City"}
>>c4=[   934
>        950
>        1095
>        708] 
>>(route,mindist)=bellman({c1,c2,c3,c4});
>>result=sprintf("Optimal route from Sacramento to ");
>>for i=2:4
>	result=[result,sprintf("%s to ",cities[i][route[i]])]
>end
>>result=[result sprintf("%s has the distance of %d miles.\n","New York",mindist)]
>>printf("%s\n",result)
Optimal route from Sacramento to Elko to Omaha to Indianapolis to New York has the distance of 2920 miles.