`(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. |

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`

`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.)
>>/* 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.