탐욕적 알고리즘 / 최소비용신장트리 / 프림 / 크루스칼 탐욕적인 접근방법 greedy알고리즘

알고리즘 탐욕적인 접근방법 greedy알고리즘

3.탐욕적인 접근방법 (Greedy 알고리즘) 현재 내 시점에서 가장 좋은 방법을 택하는것 연쇄행렬곱셈

탐욕적 알고리즘 / 최소비용신장트리 / 프림 / 크루스칼

탐욕적 알고리즘 / 최소비용신장트리 / 프림 / 크루스칼

탐욕적 알고리즘 (최소비용신장트리/프림/크루스칼)

순서대로 아이템을 선택하는데 ( 과거 미래 생각하지 않고 어떤 기준에 따라) 현재 가장 최고 라고 생각되는 것을 매번 선택한다.

(동적계획법과 마찬가지로 탐욕적 알고리즘은 최적화 문제를 푸는데 사용된다, 탐욕적인 방법이 더 간단하지만 동적계획법과 다르게 항상 최적의 해를 보장하지는 않는다)

탐욕적알고리즘 순서 ( 선택과정 -> 적정성 점검 -> 해답 점검 )

최소비용 신장트리

가중치가 최소가되는 신장트리(버텍스 모두 포함시키고 엣쥐는 (버텍스-1)개)

하나의 그래프에 하나이상의 최소비용신장트리가 존재할수 있다.

(간선의개수가 적으면 크루스칼이 유리 / 간선개수가 많으면 프림이 유리)

크루스칼 알고리즘

가중치가 작은 순서부터 싸이클을 형성하지 않는(같은그룹을 연결하지 않는) 버텍스를 연결한다