Showing posts with label graph. Show all posts
Showing posts with label graph. Show all posts

Sunday, October 7, 2012

Carpeting and Traffic light, what do they have in common? - Part 2

In the previous post, I define a carpeting problem. It quite a simple problem that can be described, including a solution in couple paragraphs. The traffic light problem is quite more complex.

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.

figure 1
If I setup the light as follow:
  1. let A go to B and C, and block every one else
  2. let B go to A and C, and block every one else
  3. let C go to A and B, and block every one else
  4. 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?