0

There are 3 popular beach resorts, A, B, and C, which reside on a line: 

                    A-----(1km)-----B-----(1km)------C.

The distances between the resorts is 1k. John owns an ice-cream truck located in beach resort A and another located in beach resort C. Two busses full of ice-cream-craving children will arrive at the beach resorts (A, B, and C) tomorrow, but John does not know for which resort each bus is headed and when each bus will arrive (the busses can arrive at different times). He plans to dispatch an ice-cream truck from its current location to a beach resort as soon as a bus arrives at that resort. Each truck can only serve a single beach resort, that is, once a truck is dispatched to a beach resort it must remain there all day. John wants to design an algorithm that minimizes the sum of distances his trucks traverse in order to reach the busses’ locations.

Show that for every deterministic algorithm ALG, there is some scenario (i.e., schedule and locations of bus arrivals) in which the total distance John’s trucks traverse under ALG is 3OPT, where OPT is the value of the optimal solution in that scenario.

4

1 回答 1

0

您已经在评论中描述了一种策略。我会稍微修改一下：

让策略是卡车停留在它们所在的位置，直到孩子们到达一个位置，然后将卡车移向那里。然后孩子们到达B，所以位于A的卡车被派往B。现在第二辆公共汽车到达A，所以我们必须将位于C的卡车派往A。卡车经过的距离总和为3公里。

对于此策略，您已经证明存在距离为3*OPT

现在想想在这种情况下还有多少其他有意义的策略（提示：没有很多）。为他们所有人描述这样一个案例，你就完成了。

于 2012-12-02T19:04:38.537 回答