복잡한 교차로를 위한 신호등 설계 알고리즘

#문제 이해

 

Design of traffic lights for a complicated junction

올바른 교차로 설계에는 두가지 조건이 필요합니다.

1. 충돌이 일어날 수 없습니다
2. 교차로의 교통을 관리하려면 최소한의 단계가 필요합니다.

 

입력: 교차점에서 가능한 모든 회전 집합
출력: 그룹의 모든 회전이 서로 충돌 없고 동시에 회전해도 되는 회전 그룹

 

 

 

사진처럼 C가 화살표 그려지면 그 방향으로 일방통행만 가능합니다.

즉 회전 가능한 경우의 수는 아래와 같습니다.
{AB, BA, CA, CB}
회전 불가능한 경우의 수는 아래와 같습니다. (일방 통행이라서)
{AC, BC}

 

 

회전이 서로 가능한 것과 안되는 것들의 집합 표

AB와 CB는 안되는 이유가 위에 차선이 서로 충돌 나기 때문이고

BA와 CA 또한 같은 이유입니다.

BA와 CB는 B에서 차가 출발하면 C에서 B로 회전하는 차랑 충돌나기 때문입니다.

---

#그래프 

 

이를 토대로 이제 그래프를 그려보겠습니다.

그래프는 Vertex 이라고 하는 점 집합과 Edge 라고 하는 점을 연결하는 선으로 구성됩니다.

Vertex = Node = 꼭짓점 = 정점

Edge = Arc = 간선

 

정점은 차들의 회전을 나타냅니다.
간선은 차들의 회전이 동시에 수행될 수 없는 꼭짓점 쌍을 연결합니다.

 

위에 표를 바탕으로 회전이 동시에 안되는 쌍을 연결한 그래프는 아래와 같습니다.

그렇다면 그래프 수준에서 신호등 문제를 해결할 수 있도록 기존 그래프 관련 알고리즘이 있을까요?

 

---

#그래프 컬러링

그래프를 색칠한다는 것은 그래프의 각 정점(꼭짓점)에 색을 할당하여 

간선으로 연결된 두 꼭짓점이 같은 색이 되지 않도록 하는 것입니다.

가능한 한 적은 색상을 사용하여 호환되지 않는 회전 그래프를 색칠하면 신호등 문제가 해결됩니다.

 

아까 위에 그래프를 다시 한번 봅시다.

 

보다시피 서로 회전할 시 충돌 나는 것들은 x 표시 되어있습니다.

이 친구들은 서로 다른 색깔로 색칠하면 되겠네요.

 

그리고 이걸 도로 그림에 그려본다면 아래와 같습니다.

서로 다른 색깔은 다른 신호등 색이라고 생각하면 문제가 해결된 모습을 볼 수 있습니다.

또한 그래프 관련 솔루션을 통해 원래 문제, 특히 복잡성과 관련된 문제를 더 잘 이해할 수 있습니다.

---

그래프 채색은 매우 어려운 문제로 알려져 있습니다. 

이는 당면한 문제에 대한 최적의(최상의) 솔루션을 찾는 데 계산 비용이 매우 많이 들 수 있음을 의미합니다.
그래서 우리는 신호등 문제도 어려운 문제라는 것을 알고 있습니다.

---

다른 문제들도 풀어서 한번 연습해보시는걸 추천드립니다.

해밀턴 경로 문제: 각 꼭지점을 정확히 한 번만 방문하는 무방향 또는 방향 그래프에 경로가 있습니까?

배낭 문제: 각각의 질량과 가치가 있는 일련의 항목이 주어지면 총 무게가 주어진 제한보다 작거나 같고 총 값이 가능한 한 커지도록 컬렉션에 포함할 각 항목의 수를 결정합니다.

여행하는 외판원 문제: 도시 목록과 각 도시 쌍 사이의 거리가 주어지면 각 도시를 정확히 한 번 방문하고 출발 도시로 돌아오는 최단 경로는 무엇입니까?

문제 목록:
http://en.wikipedia.org/wiki/List_of_NP-complete_problems