Traffic light setting: I want to setup a traffic light on a intersection (figure 1), which A, B, and C are two-way streets, while D is a one way street, and have to make sure that every one can get thought the intersection safely.
If I setup the light as follow:
- let A go to B and C, and block every one else
- let B go to A and C, and block every one else
- let C go to A and B, and block every one else
- let D go to A, B and C and block every one else.
There will be 4 turns signal for each cycle. I ensure that every one get their turn, and pass through the intersection safely.
You may notice that while we let A go to B and C, in the same time C can safely go to A. This raise the question, can we do 3 turns signal in each cycle, and still let every one get through safely?
Let start by draw a picture that will help answer the question.
This picture shows different car directions and relations between them. For example, If I let cars go from D to B (DB), then I can let the car go from D to C (DC), but I can not allow any cars from B to A (BA), or C to A (CA). The cars will crash!. In the picture, I use the red line to connect between directions that can not be allowed at the same time.
I apply this rule to all possible directions, and I get this picture:
Please note that I did not draw AB, BC, or DA, they are right turn. If the drivers are carefully turn, it's always possible. With this picture, I can setup the signal only 3 turn per cycle, as follow:
- let C to B, and D to B
- let B to A, and C to A
- let A to C, and D to C.
and still guarantee every one get through safely.
More importantly, It's also show that I can not do better than 3 turns! Why?, consider the BA, CB, and AC. If I allow one of these direction, I can not allow the other two. It's has to be at least 3 turns to allows all three directions to get through.
The picture, some what, look similar to the picture I draw for the carpeting problem, isn't it? That true because, with some preparation, I end up with the same graph coloring problem. For the carpeting, the preparation is quite easy, but not so for the traffic light setup.
Next time I come back with more discussion.
Post a Comment