hws2006   1달 전

Q. 2차원 좌표(x,y)에서 반지름이 1인 원 ((0,0) 기준) 안에서 V개의 랜덤한 point를 생성한 후에, 그 V개를 완전 그래프로 만듭니다.(complete graph: 모든 vertexes 가 서로 연결되어 있습니다. )

d8ecc31dc643cd6d2abec6e42f2077cd.png1f64ce7eddc32f1034ae59ebe91ec92a.png


아시는 분들은 다 아시겠지만, 첫번째 그림이 완전 그래프 입니다. 이 완전 그래프에서 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)의 부분입니다. 혹시 제 설명이 이해가 안가시면 코드가 더 편하실수도,,

23a6dbf7b6218e3a6f8715bfb8510685.png


sksdong1   1달 전

크루스칼 쓰면 될 거 같은데요...

jseo   1달 전

구글링을 좀 해보니까 주어진 점들에 Delaunay triangulation을 만들고 MST 알고리즘을 돌리면 된다고 나와있네요.

시간 복잡도는 O(n log n)에 공간 복잡도는 O(n) 입니다.

https://en.wikipedia.org/wiki/Euclidean_minimum_sp...

http://www.cs.uu.nl/docs/vakken/ga/slides9alt.pdf

koosaga   1달 전

아마 학교 숙제인 거 같은데... delaunay triangulation을 VlgV에 만들면 풀 수 있는게 맞긴 한데 의도된 해법은 아니라고 생각합니다. 크기 1인 원 안에 있고 랜덤하다는 성질을 활용해야 할 겁니다.

다양한 풀이가 있는데 저는 이런 풀이를 시도해 봤을 거 같네요. 실험을 해봐야 아는 거기 때문에 확실한 거는 아닙니다. 스패닝 트리 상에 들어가는 최대 길이의 간선의 길이를 P라고 대충 손으로 정하고, 거리 P 이하의 점 쌍을 모두 n^2보다 빠른 적당한 시간 안에 구한 후, 크루스칼 알고리즘으로 스패닝 트리를 구해봅니다. 만약에 스패닝 트리가 없다면, P를 조금 늘려서 다시 돌려봅니다. 있다면, 그 스패닝 트리가 정답입니다. 크루스칼 알고리즘으로 구하는 스패닝 트리는 스패닝 트리 상에 들어가는 최대 길이의 간선의 길이를 최소화하기 때문에, 알고리즘은 옳은 답을 찾습니다.


(그리고, prim's algorithm을 돌리는데 왜 O(n^2) 메모리가 필요한가요? 인접 행렬이 필요하지 않은데..)

댓글을 작성하려면 로그인해야 합니다.