Robert Blue is trying to find a parking place near his favorite restaurant. He is approaching the restaurant from the west, and his goal is to park as nearby as possible. The available parking places are pictured in Figure 2. Robert is nearsighted and cannot see ahead;

he can only see whether the space he is at now is empty. When Robert arrives at an empty space, he must decide whether to park there or to continue to look for a closer space. Once he passes a space, he cannot return to it. Robert estimates that the probability that space t is empty is pt. If he does not end up with a parking space, he is embarrassed and incurs a cost M (M is a big positive number). If he does park in space t, he incurs a cost |t |. Show how Robert can use dynamic programming to develop a parking strategy that minimizes

his expected cost.

Transcribed Image Text:

FIGURE 2 Location of Parking Places 2 T 0 = Restaurant 2...