기말 Greedy_approach 정리

Greedy algorithm 

: Make a sequence of choices, each of which simply looks the best at the moment 

선택들 중에서 그 순간 가장 좋아보이는 선택을 함. 

 

대표적인 그리디 알고리즘의 예시는 '동전 고르기' .

ex) 730 원을 채우기 위해 동전을 선택하자.

 

Greedy approach vs Dynamic programming 

-최적화 문제를 푸는데 사용(Solve optimization problems)

-그리디 알고리즘은 다이나믹 프로그래밍과 달리 문제를 작은 부분 문제로(sub-problems) 나뉘어지지 않음. 

• 지역적 최적화
• 선택을 하면 재고려하지 않음
• 선택은 과거나 미래 선택에 영향을 미치지 않음
• 최적화인지는 증명해야함(proven)

 

Greedy approach 순서

1. Selection procedure
2. Feasibility check
3. Solution check

 

Minimum Spanning Trees

:Spanning Tree 는 신장트리로 모든 정점을 포함하는 트리

이 MST 는 간선의 가중치 합이 최소인 것을 의미

 

Prim's Algorithm

:MST 를 구하는 알고리즘 

프림 알고리즘은 BFS와 같이 시작점을 기준으로 간선이 확장해나가는 방식.

차이는 프림 알고리즘에는 간선에 가중치가 있고, 최소한의 비용을 갖는 트리를 만들어야함.

 

sudo code

 

Greedy 알고리즘은 최적화에 대한 검증이 필요함. 

 

먼저 아래를 만족 시켜야 함.

G는 무방향 가중치 그래프 

F는 E 의 부분집합

Y는 V의 부분 집합 

e 는 최소화 간선이다. (방문한)Y의 정점 Vy와 (아직 방문하지 않은) V-Y의 정점 Vx , 방문한 간선 e 

 

증명을 위한 보조정리 Proof of Lemma 4.1

F가 유망하다 - (V, F') 는 반드시 최소화된 신장트리 

만약 F'에 e 포함, F와 e 포함 -> F U {e} 는 유망하다.

만약 e 가 F'가 아니면 F'U{e} 는 반드시 사이클을 포함한다.

이 e 를 F' 에서 빼면 그건 신장트리가 된다.

 

 

이게 지금 이해가 안가니깐.. 내일 다시 보기