Optimal Routing

Usage notes

A sales manager has to find out the most cost-effective route of his products from a city A to a city K. The route consists of several sections of different costs.

Use Dynamic Programming to solve the following tasks.

Some settings:
S = {A,B,C,D,E,F,G,H,I,J,K}: Set of all cities
P(x): Set of all predecessors of city x
c(x,y): Cost from city x to city y
m(x): minimal cost from city A to city x

a)

Fill in the following blanks:
The objective function to be minimized is described by the ___________________ from city ___________________ to city ___________________ . After solving the problem of the optimal routing the optimal cost will be given by the expression ___________________

b)

Determine the optimality equation:
Given a set b, use the notation min[a,b](c) to describe the minimum of c over all a $\in$ b . Denote by y a possible predecessor of x . Don't use spaces.

m(x) = ___________________

Look at the following algorithm written in pseudo code, which solves the problem of the optimal routing, and try to understand it.

m(A) := 0
S := S\{A}
repeat
  choose x in S with m(y) defined over all y in P(x)
  m(x) := min[y,P(x)](m(y)+c(y,x))
  b(x) := y that leads to the minimum
  S := S\{x}
until S = {}
output m(K)

c)

Perform the first step of the algoritm:

m(B) = ___________________ b(B) = ___________________

Perform the other steps:

m(C) = ___________________ b(C) = ___________________
m(D) = ___________________ b(D) = ___________________
m(E) = ___________________ b(E) = ___________________
m(F) = ___________________ b(F) = ___________________
m(G) = ___________________ b(G) = ___________________
m(H) = ___________________ b(H) = ___________________
m(I) = ___________________ b(I) = ___________________
m(J) = ___________________ b(J) = ___________________
m(K) = ___________________ b(K) = ___________________

d)

Finally, you get the optimal route by ___________________ using the function ___________________ starting from the city ___________________

e)

Determine the optimal route and the optimal cost:

optimal route:A -> ___________________ -> ___________________ -> ___________________ -> K

optimal cost = ___________________

Home

Feedback to quiz developers, problem reports...please use it!!!

Name:
	Restore previous session, if applicable Start blank quiz
Note:	If you wish to ask for a hint or a solution, or if you want your answers checked, you have to log in. Your answers, or the fact that you asked for a hint or solution, may be recorded.