Every morning I need to commute to a specific room for my analysis course; however, it is disappointing that I usually cannot leave my home early enough for me to guarantee I would not be late for class. Roughly, it will take me 14-15 minutes to arrive at the room, and the course has usually started for 2-3 minutes. This motivates me to come up with the topic: how can I optimize my commuting time so that I can ensure myself that I am not going to miss any information provided in the beginning of the class.
We will first disregard the obvious shortest path problem involved here as I believe I am going through the shortest path between my home and the specific room. Nevertheless, it is still worth discussing so we will put it in a later paragraph. For now, I would like to address the decisions I made when I met green lights and red lights. The figure below shows the general pattern of routes to classroom I walk through every morning. The green squares represent the traffic lights; and the red lines represent the zebra crossings; and the blue lines represent pedestrians; and the pink line is a special crossing we will discuss later; and the black square is the location of the specific room I am heading for. Note that I start from the green square in the right corner of the figure and the upper side is North.
Route to Classroom
As of before, I used a "greedy" way to determine in which direction I should go. Every time I stand at a green spot in above figure, I quickly judge the following conditions and make corresponding moves:
1. If I can go to north side, i.e. the traffic light is green/ the side is a pedestrian/ I reached the leftmost part of the route (the left corner green spot), then I will go north (wait for traffic light if needed).
2. Otherwise
2.1. If the west side is a pedestrian, i.e. the left side of the spot is a blue line, then I will walk through the blue line to the next green spot.
2.2. If the west side is also a zebra crossing, then I will walk through the crossing.
I always believed that with the above decision processes, I will arrive at the classroom in the shortest time; however, recent experiences have changed my mind a little bit and made me believe that this should be a dynamic programming issue rather than a situation that can be easily solved by specially structured greedy algorithm. This is actually because for several consecutive days, every time I crossed to the north side of the street in the first decision I make everyday, meaning that I go from the right corner green spot to the green spot above it, and I always took it fortunately. Unfortunately, successive events always did not happen in expected ways. For every single time I met the traffic light walking through west on the street, I never met a green light; and whenever I recalled the time I took to cross the street in my first decision, I could repeatedly simulate what would happen if I did not cross the street. That is: I would meet green light in the south side of street, and the only possible red light I might meet was only when I reached the leftmost part of the route and needed to go north, which would not take more than a minute.
These days, after collecting data of the time it took for those red lights turning to green lights, together with the estimated time I need to walk through all those pedestrians, I want to figure out whether or not my previous usage of greedy algorithm is the generally efficient way for me to make decisions.