탐욕법
Greedy 알고리즘이라고 부르는 이 방식은 최종 해답을 찾기 위해 각 단계마다 하나의 답을 고르고 그 답들을 모아서 결과적으로 최적의 답을 고른다는 문제이다.
하지만 최적화 문제에서
- 선택할 당시는 최적의 답이지만
- 그 답이 최적임을 보장하지는 못함
이러한 문제가 발생 할 수 있다.
하지만 이러한 탐욕법도 상대적으로 설계하기가 매우 쉽고 수가 엄청 큰 경우 DP같은 방법을 이용할 수 없음. 이럴 때 huristic하게 답을 찾아낼 수 있다.
하지만 최적화 문제에서 반드시 정확성을 증명해야함
- 이와 관련해서는 탐욕법에 대해 설명하는 글에서 자세히 쓰도록 하겠다.
최소비용신장트리 MST
문제정의
문제 : 주어진 그래프에서 최소비용 신장트리를 구하시오
엄밀한 정의 :
-
주어진 그래프: 𝐺 = (𝑉, 𝐸) G는 모든 정점이 연결된 가중치가 있는 무방향 그래프
-
신장트리(spanning tree): 𝐺의 부분 그래프 T = (𝑉, 𝐹), F는 E에 포함된다.
• 그래프 𝐺의 모든 정점을 연결하는 트리: 간선의 개수는 𝑛 − 1 -
최소비용 신장트리(MST) = 모든 신장트리 T중에서 가중치의 합이 최소가 되는 신장트리
Brute-Force
- 모든 신장트리를 찾아서 가중치의 합이 가장 작은것을 선택
- 신장트리를 찾는 법
- 간선의 개수가 n-1인 연결된 트리(acyclic)가 될 때 간선을 하나씩 제거
Greedy Approach
1단계 : 초기화
해답의 집합을 공집합으로 둔다
- 간선 집합 E의 부분집합 F를 공집합으로 둔다
2단계(선택): 최적의 원소 하나를 해답의 집합에 포함시킨다.
- 𝐸에서 최적의 간선 하나를 추출해서 𝐹에 포함시킨다.
- 최적을 선택하는 방법? 프림 vs 크루스칼
3단계(검사): 해답의 집합이 최종이면 종료, 아니면 2단계를 반복한다.
- 간선의 부분 집합 𝐹의 원소 개수가 𝑛 − 1이면 최종 해답
코드
def prim(W):
n = len(W) - 1
F = []
nearest = [-1] * (n + 1) # 근접한 노드 보여주기위함
distance = [-1] * (n + 1) # 거리
for i in range(2, n + 1): # 1은 시작노드라서 빼고 2부터 시작
nearest[i] = 1
distance[i] = W[1][i]
print_nd(F, nearest, distance)
for _ in range(n - 1):
minValue = INF
for i in range(2, n + 1):
if (0 <= distance[i] < minValue): # 거리가 min 보다 작고 0보단 크면
minValue = distance[i] # min 변경
vnear = i # 최적의 노드값 i로 저장
edge = (nearest[vnear], vnear, W[nearest[vnear]][vnear]) # 엣지 정보 저정 (출발 노드, 도착, 노드 거릭)
F.append(edge) # add edge to F
distance[vnear] = -1 # 방문했으니 -1로 돌려버림
for i in range(2, n + 1):
if (distance[i] > W[i][vnear]): # 만약 거리가 새로운 노드간의 거리보다 크면
distance[i] = W[i][vnear] # 새로운 거리로 교체하고
nearest[i] = vnear # 연결노드 변경
print_nd(F, nearest, distance)
return F
def cost(F, W):
total = 0
for e in F:
total += W[e[0]][e[1]]
return total
def print_nd(F, nearest, distance):
print('F = ', end='')
print(F)
print(' nearest: ', end='')
print(nearest)
print(' distance: ', end='')
print(distance)
INF = 999
W = [
[-1, -1, -1, -1, -1],
[-1, 0, 1, 3, INF, INF],
[-1, 1, 0, 3, 6, INF],
[-1, 3, 3, 0, 4, 2],
[-1, INF, 6, 4, 0, 5],
[-1, INF, INF, 2, 5, 0],
]
F = prim(W)
for i in range(len(F)):
print(F[i])
print("Minimum Cost is ", cost(F, W))
m, n = map(int, input().split())
