Mathematics > Research Paper > DeVry University, Chicago - EWAN 209Repeat Joint (All)

DeVry University, Chicago - EWAN 209Repeat Joint

Document Content and Description Below

reduces to the following: Suppose the shortest path (call it R) from city 1 to city 10 is known to pass through city i. Then the portion of R that goes from city i to city 10 must be a shortest path ... from city i to city 10. If this were not the case, then we could create a path from city 1 to city 10 that was shorter than R by appending a shortest path from city i to city 10 to the portion of R leading from city 1 to city i. This would create a path from city 1 to city 10 that is shorter than R, thereby contradicting the fact that R is a shortest path from city 1 to city 10. For example, if the shortest path from city 1 to city 10 is known to pass through city 2, then the shortest path from city 1 to city 10 must include a shortest path from city 2 to city 10 (2–5–8–10). This follows because any path from city 1 to city 10 that passes through city 2 and does not contain a shortest path from city 2 to city 10 will have a length of c12 [something bigger than f2(2)]. Of course, such a path cannot be a shortest path from city 1 to city 10. Characteristic 5 If the states for the problem have been classified into one of T stages, there must be a recursion that relates the cost or reward earned during stages t, t 1, . . . , T to the cost or reward earned from stages t 1, t 2, . . . , T. In essence, the recursion formalizes the working-backward procedure. In Example 3, our recursion could have been written as ft(i) min j {cij ft1( j)} [Show More]

Last updated: 3 years ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: