minimum spanning tree2 Prim algorithm (프림 알고리즘) Prim algorithm (프림 알고리즘) 프림 알고리즘은 greedy algorithm의 일종이며, 최소신장트리 문제를 해결하기 위한 알고리즘이다. Greedy algorithm과 최소신장트리에 관한 개념은 앞 글에서 다루었다. 앞에서 그래프를 G=(V,E)로, 신장 트리를 T=(V,F)로 표기하기로 했다. 우리는 최소신장트리가 되는 F를 찾는 것이 목표다. 그래프 G는 다음과 같다. 프림 알고리즘은 한 점에서 시작하여 계속 최적의 선택을 해나간다. 그 시작점을 v1이라고 해보자. v1을 담고있는 새로운 집합 Y(최소신장트리의 vertex를 담는다.)를 만들고, 집합 F(최소신장트리의 edge를 담는다.) 는 공집합으로 초기화를 해준다. 앞으로 최적의 선택을 해가며 Y와 F를 채워나갈 것이며, 집합 .. 2019. 5. 15. Greedy algorithm(탐욕 알고리즘)/ Minimum spanning tree(최소 신장 트리) Greedy algorithm(탐욕 알고리즘) Greedy algorithm은 그 당시 "가장 최고"라고 생각되는 것을 선택한다. 각 선택은 지역적으로 최적(locally optimal)이 되는 것이다. 하지만 그 것이 전체적으로 최적(globally optimal)이 아닐 수 있다. 따라서 알고리즘이 정말로 최적의 답을 주는지 체크해야 한다. Greedy algorithm을 해결하는 방법은 총 세 가지의 단계로 이루어진다. 1. 선택과정 : 지역적으로 가장 최선의 선택을 한다. 2. 적정성 검사 : 그 선택이 문제의 조건을 벗어나지 않는 지 확인한다. 3. 해답검정 : 방금 한 선택으로 문제가 해결되었는지 확인한다. 이렇게만 설명을 하면 감이 오지 않을 수 있으니 예시를 함께 보자. 가령 500원, 1.. 2019. 5. 14. 이전 1 다음
