(complete graph: 모든 vertexes 가 서로 연결되어 있습니다. )
아시는 분들은 다 아시겠지만, 왼쪽 그림이 완전 그래프 입니다. 이 완전 그래프에서 MST (Minimum Spanning Tree, 오른쪽 그림)를 찾는것이 문제입니다..
뭐 간단하게 인접 행렬 또는 리스트 만들어서 거기에 대한 Prim's algorithm을 적용하면 구해지긴 합니다만, 문제는 vertex 개수인 V가 많이 커지게 된다면, (|V| > 30000~ 50000) Memory 문제때문에 인접 행렬 구성은 포기하게 되는 실정입니다. (왜냐면 완전 그래프라 |V|^2 크기의 행렬이 필요합니다.)
근데 이 문제가 좀 웃긴게, vertex 사이의 weight 가 주어지는것이 아닌 직접 point를 random하게 뽑고 (반지름이 1인 원 안에서) 그리고 그 사이의 거리를 알아서 구한뒤에 MST의 크기 (MST의 모든 edges 값)을 구하는 것입니다.
그래서 제가 고안해 낸 알고리즘은 다음과 같습니다,
1. 1차원 자료형에 Pair 형으로 모든 point(x,y)를 생성해서 담는다. 이것을 basket이라 부른다.
2. HashMap 형태로 <Pair Point, Value> 형으로 '1'에서 생성해낸 point를 다시 담아낸다. (Ex. <Point(x,y), Inf> ) 이것을 Graph라 부른다. 여기서 Value는 그 Point로 가기위한 최소 비용을 의미한다.
3. basket에서 랜덤하게 하나를 뽑아서 시작 포인트를 정한다.
3-1. 그 point에 속하는 Graph의 Value는 0으로 만든다.
3-2. basket에서 뽑은 Point는 삭제한다.
4. (이미 뽑은) 포인트에서 basket에 담겨져 있는 모든 포인트를 하나씩 꺼내봐서 길이를 잰다, (sqrt((x-x1)^2+(y-y1)^2)). 그 길이가 Graph에 담겨져 있는 해당 Value보다 작다면, 바꿔준다.
5. 모든 포인트를 둘러보면서 가장 작은 Value를 가진 Point를 basket에서 뽑는다. (사실 말만 뽑는거지 이미 4에서 계속 비교하면서 Point를 찾음)
6. basket에서 뽑은 Point는 삭제한다.
6-1. Point의 value는 결과 값(MST Cost)에 더해진다.
7. basket에 있는 Point가 모두 없어질때까지 (4-6)을 반복한다.
8. 결과 출력
--------------------------------------------------
이런식으로 알고리즘을 만들고 돌리게되면 V가 50000일때 200초 정도가 나옵니다. 그런데 60초 미만으로 가능하다는 얘기를 들어서, 지금도 고민하고 있습니다.
아무리 생각해도 완전 그래프이기때문에 모든 edges들을 하나씩 다 봐줘야 합니다. 그나마 최소한으로 줄일 수 있는것이 (4-6)반복 마다, basket에 있는 Point를 하나씩 없얘주기 때문에 (4-6)이 |V|^2 반복이 아닌, |V|* (|V-1|+|V-2|....+|1|) 입니다.
여기서 좀더 발전할 수 있는 여지는 없을까요?
아래의 코드는 제가 만든 (4-6)의 부분입니다. 혹시 제 설명이 이해가 안가시면 코드가 더 편하실수도,,
while(repeat):
repeat -= 1
min = 100
for (x,y) in basket:
#Distance between two nodes is the euclidean distance between the points
k = math.fabs( (verx- x ) + (very-y) )
if graph[x,y] > k: #update weight of vertex if searched way is cheaper.
graph[x,y]= k
if min > graph[x,y]: #get the vertex having minimum weight among the adjacent MST.
min = graph[x,y]
minIndex = (x,y)
if min is 100:
break
else:
result += min
basket.remove(minIndex)
(verx, very) = minIndex
글쓰기