최소비용 신장트리

20. 최소비용 신장트리#

소스코드

아래 내용을 (구글 코랩) 최소비용 신장트리에서 직접 실행할 수 있다.

주요 내용

  • 탐욕 알고리즘

  • 최소비용 신장트리: 프림 알고리즘

20.1. 탐욕 알고리즘이란?#

탐욕 알고리즘은 선택 순간의 최적인 대상을 선택하는 기법이다. 동적계획법과 마찬가지로 최적화 문제를 풀기 위해 주로 사용된다. 탐욕 알고리즘의 작동방식은 다음과 같다.

  1. 공집합에서 출발하여 아래 과정을 반복하면서 문제의 해답을 얻을 때까지 집합에 원소를 추가한다.

    • 선택과정: 지정된 기준에 따라 집합에 추가할 최적의 원소 선택

    • 적절성 검사: 선택된 원소가 추가된 새로운 집합의 적절성 판단

    • 해답점검: 새로운 집합이 문제의 해답인지 여부 판단

    • 해답이면 종료. 아니면 선택과정으로 돌아가기

  2. 최종적으로 얻어진 집합이 최적의 해인지 여부를 확인한다.

마지막에 최적의 해 여부를 확인해야 하는 이유는 아래 예제가 보여주듯이 탐욕 알고리즘이 항상 최적의 해답을 제시하는 것은 아니기 때문이다.

Example 20.1 (거스름돈 문제)

거스름돈을 돌려주기 위해 필요한 최소한의 동전 개수를 알아내는 문제다. 단, 사용할 수 있는 동전은 500원, 250원, 100원, 50원, 10원 5 종류이다.

거스름돈 문제를 탐욕 알고리즘으로 해결하려면 가장 큰 액수의 동전부터 최대한 많이 사용해야 한다. 예를 들어, 360원을 지불하기 위해서 사용하는 동전은 다음과 같다.

500원: 0개
250원: 1개
100원: 1개
50원: 0개
10원: 1개

이 경우엔 탐욕 알고리즘 기법으로 항상 동전의 개수가 최소가 되도록 거스름돈을 돌려줄 수 있다. 하지만 자세한 증명은 생략한다. 그런데 만약에 160원을 거슬러주기 위해 사용할 수 있는 동전 종류가 120원, 100원, 50원, 10원 짜리만 있다고 가정하자.

탐욕 알고리즘을 적용하면 120원 동전 1개, 10원 동전 4개 총 5개의 동전이 필요하다. 반면에 최적의 해법은 100원 동전 1개, 50원 동전 1개, 10원 동전 1개 총 3개의 동전만 있으면 된다. 즉, 탐욕 알고리즘으로 얻어진 해가 최적이 아니다.

20.2. 최소비용 신장트리#

가중 비방향그래프

가중 비방향 그래프가 다음과 같이 주어졌다고 가정하자. 즉, 마디 사이의 이음선에 방향이 없다.

연결그래프

위 그래프는 모든 마디 사이에 경로가 존재하는 연결그래프이다.

단순 순환경로와 트리

단순 순환경로는 하나의 마디에서 출발하여 다시 돌아오는 경로에 서로 다른 세 개의 마디가 있고, 해당 경로상의 모든 마디가 서로 다른 경로를 가리킨다. 즉, 출발점을 제외한 다른 마디에서의 순환 경로가 없어야 한다.

비순환 비방향그래프는 단순순환경로를 전혀 포함하지 않는 비방향그래프를 의미하며, 연결 비순환 비방향그래프를 트리라 부른다.

신장트리

가중 비방향 연결그래프 \(G\)가 주어졌다고 가정하자. 그러면 \(G\)의 신장트리spannin\(G\) tree는 \(G\)의 마디는 그대로 두면서 이음선의 일부를 제거하여 만들어진 트리를 가리킨다. 신장트리에 포함된 이음선의 가중치들의 합이 최소인 \(G\)의 신장트리를 \(G\)의 최소비용 신장트리라 부른다. 여러 개의 최소비용 신장트리가 존재할 수 있다.

Example 20.2 (그래프와 신장트리)

최소비용 신장트리 활용 예제

  • 도로건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제

  • 통신: 통신선의 길이가 최소가 되도록 통신케이블 망을 구성하는 문제

  • 배관: 배관의 총 길이가 최도가 되도록 연결하는 문제

20.3. 프림 알고리즘#

가중 비방향 연결그래프 \(G = (V, E)\)가 주어졌을 때 \(G\)의 최소비용 신장트리를 프림Prim 알고리즘으로 찾으려 한다. 여기서 \(V\)는 마디들의 집합, \(E\)는 이음선들의 집합을 가리킨다.

기본 아디이어

\(Y = \{ v_1 \}\)와 \(F = \emptyset\) 두 집합을 아래 과정을 반복하여 확장해 나간다. \(v_1\) 대신 임의의 다른 마디로 시작해도 상관 없다.

  1. \((V-Y)\)에 속한 마디 중에서 \(Y\)와 가장 가까운(최소거리) 마디 선택해서 \(Y\)에 추가한다.

  2. 해당 마디 선택에 사용된 이음선을 \(F\)에 추가한다.

  3. \(Y == V\) 인 경우 종료하고, 아니면 처음으로 돌아간다.

Example 20.3 (프림 알고리즘 적용)


프림 알고리즘의 최적여부 증명

프림 알고리즘이 항상 최소비용 신장트리를 생성하는지 증명해야 한다. 먼저 프림 알고리즘의 결과가 신장트리라는 것은 확실하다.

  • \(V == Y\) 일 때 종료하기에 모든 마디가 서로 연결된다.

  • 단순순환경로가 존재하지 않는다. 이유는 항상 새로운 마디가 집합 \(Y\)에 추가되기 때문이다.

하지만 최소비용 신장트리 여부는 불확실하다. 프림 알고리즘으로 생성된 신장트리가 최소비용 신장트리라는 것을 증명하기 위해 유망한 이음선 집합 개념을 활용한다. 가중 비방향 연결그래프 \(G = (V, E)\)가 주어졌을 때 이음선 부분집합 \(F \subseteq E\)에 이음선을 추가하여 최소비용 신장트리를 만들 수 있다면, \(F\)는 유망하다(promissing) 라고 부른다.

프림 알고리즘이 항상 최소비용 신장트리를 생성한다는 사실은 아래 사실로부터 따라온다.

보조정리

  • 전제 1: \(G = (V, E)\) 이고 \(F (\subseteq E)\)는 유망함.

  • 전제 2: \(Y\)는 \(F\)에 사용된 마디들의 집합

  • 전제 3: \(Y\)에 있는 정점과 \((V-Y)\)에 있는 정점을 잇는 이음선 중에서 가중치가 가장 적은 이음선 중에 하나가 \(e\).

  • 결론: \(F \cup \{ e \}\) 또한 유망함.

보조정리 증명 (그림으로 설명)

프림 알고리즘 구현

from math import inf
from collections import defaultdict

def prim(W):                    # W: 가중 비방향 연결그래프의 인접행렬

    m = len(W)                  # 마디 개수: 인접행렬의 행의 인덱스를 마디 이름으로 사용. v(0), ..., v(m-1)
    F = defaultdict(list)       # 신장트리에 포함될 이음선들의 집합
                                # 키: 마디, 키값: 추가되는 이음선에 사용된 다른 마디들의 리스트
                                # 예제: {0: [1, 2], 2: [4, 3]}
    
    # 업데이트되는 Y는 직접 언급되지 않음. 이유는 F에 Y에 대한 정보가 함께 포함되기 때문임.
    
    # nearest와 distance를 업데이트 하면서 Y를 업데이트할 때 필요한 정보를 저장함.
    # i는 range(m-1)에서 움직임. 즉, v(0), ..., v(m-1)를 가리킴
    
    # nearest[i]: 생성중인 신장트리 Y에 속한 마디 중 v(i)에 가장 가까운 마디. 
    # 시작은 v(0). 이유는 신장트리 Y에 v(0)가 포함되었다고 가정했기 때문임.
    nearest = [0] * m
    
    # distance[i]: nearest[i]와 v(i)를 잇는 이음선의 가중치. 
    # -1이면 이미 신장트리에 포함된 것으로 간주
    # 시작은 v(0) 과의 이음선의 가중치. 
    distance = [W[0][i] for i in range(m)]  
                                            
    # V0 는 이미 포함되어 있다고 가정
    distance[0] = -1
    
    # 신장트리에 속할 이음선을 모든 마디가 선택될 때가지 하나씩 추가
    for _ in range(m-1):
    
        # distance 정보를 이용하여 아직 신장트리 Y에 속하지 않으면서 가장 가까운 마디 선택
        min = inf
    
        for i in range(1, m):
            if (0 < distance[i] < min):    # Y에 속하지 않는 마디 중 가장 가까운(최소 가중치) 마디 선택
                min = distance[i]          # 거리
                vnear = i                  # 선택된 마디
    
        # 선택된 마디와 가장 가까운 마디 사이의 이음선을 신장트리에 추가
        F[nearest[vnear]].append(vnear)
        distance[vnear] = -1    # 선택된 마디 표시
    
        # 아직 Y에 포함되지 않은 마디를 대상으로 distance와 nearest 업데이트 (F가 수정되었기 때문)
        for j in range(1, m):
            if W[j][vnear] < distance[j]:   # Y에 새로이 추가된 vnear와의 거리가 최소 가중치 값을 갖는 경우
                nearest[j] = vnear          # v(j)에 가장 가까우면서 Y에 속한 마디는 v(vnear)
                distance[j] = W[j][vnear]   # v(j)와 v(vnear)의 거리
    
    return F 

W = [[0,   1,   3,   inf, inf],
     [1,   0,   3,   6,   inf],
     [3,   3,   0,   4,   2  ],
     [inf, 6,   4,   0,   5  ],
     [inf, inf, 2,   5,   0  ]]

prim(W)

defaultdict(list, {0: [1, 2], 2: [4, 3]})

참고

PythonTutor: 프림 알고리즘 예제에서 위 알고리즘을 직접 실행하면서 F의 변화를 확인할 수 있다.

프림 알고리즘 일정 시간복잡도 분석

  • 입력크기: 마디 수 \(n\)

  • 단위연산: 중첩 반복문 안에 있는 비교 명령문

  • 일정 시간복잡도: \(n-1\) 번 반복되는 명령문 두 개가 \(n-1\)번 반복되는 반복문 안에 들어 있음. 따라서 다음이 성립:

    \[ T(n) = 2(n-1)(n-1) \in O(n^2) \]

20.4. 연습문제#

  1. (실습) 최소비용 신장트리

Contents