undefined

Assignment #4 Our problem deals with a hypothetical 19th-century stagecoach company that transports passengers from California to New York. Although the starting point (California) and the destination (New York) are fixed, the company can choose the intermediate states to visit in each stage of the trip. We assume that the trip is completed in four stages (legs) where stage 1 starts in California, stage 2 starts in one of three states in the Mountain Time Zone (say, Arizona, Utah or Montana), stage 3 starts in one of three states in the Central Time Zone (say, Oklahoma, Missouri or Iowa) and stage 4 starts in one of two states in the Eastern Time Zone (North Carolina or Ohio). When stage 4 ends, the stagecoach reaches New York, which is the final destination. Since in those days travel by stagecoach was rather dangerous because of attacks by roaming criminals, life insurance was offered to the traveling passengers. Naturally, the cost of the insurance policy was higher on those portions of the trip where there was more danger. The stagecoach company thus faced the problem of choosing a route that would be cheapest and thus safest for its passengers. The nodes in the diagram below are denoted by (i, j) where i corresponds to a stage (i= 1, 2.... 5) and j corresponds to a state j in stage . Given the state j in stage i, the decision to travel to state k in the next stage i+1 results in a cost (i.e., insurance premium) of ck). These costs are indicated next to the arrows corresponding to each decision. For example, c1(2) = 4 and c2 (3) = 6. Find the route that results in the minimum cost. (2,3) (3,3) \1 14 (4,2) 72 16 5 (1,1) ->4 (2, 2) -+7 \ 4 \ 8 73 - 2 \ 4 26 11 -74 (3,2) (5,1) 3 3 24 (4,1) 73 13 |(2,1) (3,1)