Difference between revisions of "TADM2E 1.3"

From Algorithm Wiki
Jump to: navigation, search
(Corrected the graph figure.)
 
Line 20: Line 20:
  
 
So the distance from ''a'' to ''b'' through ''d'' is 10 miles. Assuming you drive 30 miles per hour, the time to travel this would be 20 minutes, but due to the busy intersection at ''d'', you are delayed 15 minutes, the total time would be 35 minutes.
 
So the distance from ''a'' to ''b'' through ''d'' is 10 miles. Assuming you drive 30 miles per hour, the time to travel this would be 20 minutes, but due to the busy intersection at ''d'', you are delayed 15 minutes, the total time would be 35 minutes.
 +
 +
---
 +
 +
Another possible solution: You have a longer route with a higher speed and a shorter route with a lower speed. By choosing the numbers appropriately, you can make the longer route be the winner. The speed may be due to law, or due to traffic jam, or because of pot holes on the road :-)
 +
 +
Suppose road of length l1 has speed limit s1 and another road of length l2 has speed limit l2. The shorter route is determined by comparing l1 with l2. The faster route is determined by comparing l1/s1 with l2/s2. With positive numbers, if l1 > l2 but l1 < l2 * s1 / s2, then the faster route differs from the shorter route.
  
  
 
[[introduction-TADM2E|Back to ''Introduction ...'']]
 
[[introduction-TADM2E|Back to ''Introduction ...'']]

Latest revision as of 07:32, 12 September 2015

  a ----------- c ----------- b
   \                         /
    \--------- d ---------- /

If the distance from a to b going through d is less than the distance from a to b going through c but there is a busy traffic intersection at d with a stop sign that is always backed up, then the route from a to b through c is faster, but the route through d is shorter.


For example,

$ dist(a, c) = 10 $ miles

$ dist(c, b) = 5 $ miles

So the distance from a to b through c is 15 miles. Assuming you drive 30 miles per hour, the time to travel this would be 30 minutes


$ dist(a, d) = 5 $ miles

$ dist(c, b) = 5 $ miles

So the distance from a to b through d is 10 miles. Assuming you drive 30 miles per hour, the time to travel this would be 20 minutes, but due to the busy intersection at d, you are delayed 15 minutes, the total time would be 35 minutes.

---

Another possible solution: You have a longer route with a higher speed and a shorter route with a lower speed. By choosing the numbers appropriately, you can make the longer route be the winner. The speed may be due to law, or due to traffic jam, or because of pot holes on the road :-)

Suppose road of length l1 has speed limit s1 and another road of length l2 has speed limit l2. The shorter route is determined by comparing l1 with l2. The faster route is determined by comparing l1/s1 with l2/s2. With positive numbers, if l1 > l2 but l1 < l2 * s1 / s2, then the faster route differs from the shorter route.


Back to Introduction ...