태그 : SpanningTree

최소비용 신장 트리... Prim Minimum Cost Spanning Tree

 이번 과제는 최소비용 신장트리를 얘기할 때 항상 크루스칼 알고리즘과 함께 얘기되고, 비교되는 프림 알고리즘이다. 크루스칼 알고리즘에 비해서는 이해하기 쉬운 편이다. 각 변수에 어떤 값이 들어가는지 몇번 찍어(적어)보다 보면 금방 이해가 된다.

 프림 알고리즘의 원리는 어떻게 보면 크루스칼 알고리즘 보다 더 수월하다. 보통 사람이 생각하는 방식으로 답을 찾기 때문이다.
  1. 그래프 W에서 시작 정점을 선택한다.
  2. 선택한 정점에 부속된 모든 이음선 중에서 가중치가 가장 작은 이음선을 연결하여 트리를 확장한다.
  3. 이전에 선택한 정점과 새로 선택한 정점에 부속된 모든 이음선 중에서 가중치가 가장 작은 이음선을 삽입하는데, 사이클을 형성하는 이음선은 삽입 할 수 없으므로 그 다음으로 가중치가 작은 이음선을 선택한다.
  4. 그래프 W에 n-1개의 이음선을 삽입할 때 까지 3.을 반복한다.
  5. 그래프 W에 이음선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.
 참고 자료에 있는 책을 참고하면 크게 어렵지 않게 짤수 있다. 시간 복잡도는 이음선의 갯수가 많을 수록 프림 알고리즘의 효율이 좋아진다. 하지만 개인적으로는 짜는데 고생한 만큼 크루스칼 알고리즘이 마음에 든다.
프림 최소비용 신장트리 알고리즘

by sakuragi | 2007/05/03 02:10 | :: R space :: 과제 | 트랙백 | 덧글(11)

최소비용 신장 트리... Kruskal Minimum Cost Spanning Tree

 최근 알고리즘 관련 포스팅을 하면서 부터 방문자는 부쩍 늘었는데, 어찌된 것인지 덧글은 더더욱 줄어든 느낌이다. 소스를 보고, 과제로 제출하거나, 참고하는 것도 좋지만 덧글도 좀 남겨주길...

 플로이드나 연쇄행렬 알고리즘의 경우 동적 계획법이였다. 이번의 크루스칼 최소비용 신장 트리의 경우는 탐욕적인 방법으로 분류되는 알고리즘이다. 동적 계획법이 과거의 결과를 현재에 재사용하는데 중점을 둔 기법이였다면, 탐욕적인 방법은 과거나 미래는 생각하지 않고, 현재 가장 최적이라고 생각되는 결과만을 취한다. 그래서 어떤 경우에도 현재의 최적이라고 생각되는 결과를 취하지만, 최종적으로 결과를 종합 했을 때, 그 결과가 꼭 최적인 된다고는 볼 수 없다. 크루스칼 최소비용 신장 트리 알고리즘의 경우 언제나 최종적인 결과도 최적이 된다(고 책에 나온다).

 크루스칼 알고리즘의 원리는 어렵지 않다. 간단하게 얘기하면 다음의 네가지 과정이 전부다.
  1. 그래프 G의 모든 이음선을 가중치에 따라 오름차순으로 정렬한다.
  2. 그래프 G에 가중치가 가장 작은 이음선을 삽입하는데 이때 사이클을 형성하는 이음선은 삽입할 수 없으므로 그 다음으로 가중치가 작은이음선을 삽입한다.
  3. 그래프 G에 n-1개의 이음선을 삽입할 때까지 2.를 반복한다.
  4. 그래프 G의 이음선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.
 이 과정 중에 사이클을 형성하는 이음선을 삽입할 수 없다는 조건에서, 아래의 소스에서는 서로소의 개념이 들어간다. 참고자료의 pseudo code를 바탕으로 짰으니, 그 책을 보면서 보면 좀 더 쉽게 이해할 수 있을 것 이다. 여기서의 입력 역시 참고자료에 나오는 책에 있는 예이다.
크루스칼 최소비용 신장트리 알고리즘

by sakuragi | 2007/05/02 01:21 | :: R space :: 과제 | 트랙백(1) | 덧글(32)

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: