![]() ![]() Can you show that there is no faster solution?Ĥ. Now try to find a 14-minute solution for the six-vehicle-per-column, 13-by-13 grid problem in figure 1.ģ. Suppose you must keep the columns of cars in order and they all must go through the center. It's easy to see that there are no crashes.ġ. How can we arrange it so all vehicles cross their target edges in four minutes?Īll the routes are shown here in figure 3:Īll vehicles exit their opposite edges after four minutes. So, B wants to cross the bottom edge R wants to cross the right edge, and so on. Warm-Up: Consider a situation in which each column consists of a single vehicle as shown in figure 2:Īgain, each vehicle wants to exit the opposite edge. ![]() For concreteness, suppose that there are six vehicles of each color and the grid is 13-by-13 in dimension. ![]() The question is how to arrange the movements so that all vehicles traverse their target sides in as short a time as possible. You want to avoid crashes.Īs figure 1 shows, the four columns are converging onto the single central square, so if they all advance toward the center at once, there will be a crash. If two vehicles end up in the same cell, they crash. A vehicle can move to its vertically or horizontally neighboring cell in one minute. Within a column, neighboring vehicles are in neighboring cells. Each vehicle is in one grid cell location. In doing so, the vehicles may move side-by-side rather than in single file.īecause we've made the problem harder by allowing four columns, we'll make the rules of movement simpler. So the Greens want to exit through the top side, the Oranges want to exit through the left side and so on. The columns are about to meet at an intersection as shown in figure 1.Įach column wants to exit the border of the rectangle on the side opposite from where it comes. Suppose there are four columns of vehicles, each of a different color. Let's start by making the problem a little harder. There are much more efficient ways to have two columns cross one another, when you are not limited to roads. The fact is, though, that he was a bad traffic cop. Bradley mockingly praises Patton's skills as a traffic cop. After a few minutes, he is called back to his higher responsibilities by Omar Bradley. In frustration, Patton leaves his jeep and starts directing traffic. In the movie Patton, the General sees two columns of his tanks crossing paths and getting stuck in gridlock. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |