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