justgo_developer

Greedy Alg.경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다. §해를 구하는 일련의 선택 과정마다 §그 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 §결과적으로 전체적인 최적해를 구할 수 있을 것이라고 희망적인 전략을 취하는 방법 –희망적 à 각 단계마다 선택한 최적해가 전체 최적해를 만들어 내지 못할 수 있음을 의미 §동작 과정 1.해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합(solution set)에 추가 2.실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사 3.해 검사: 새로운 부분해 집합이 문제의 해가 되는지 확인; 아직 전체 문제의 ..

크루스칼 알고리즘(Kruskal's Algorithm) - 에지들을 가중치의 오름차순으로 정렬한다.- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다.- n-1개의 에지가 선택되면 종료한다.노드가 9개이므로 에지가 8개까지만 하면 된다. 더하면 사이클이 생김.◆ 사이클 검사- 초기 상태 : 선택된 에지 없음- 각각의 연결요소를 하나의 집합으로 표현{a} {b} {c} {d} {e} {f} {g} {h} {i} MST-KRUSKAL(G, w)A

최소 스패닝 트리(Minimum Spanning Tree, MST)란? 최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다. 이때 생성되는 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지 못한다. Generic MST 알고리즘- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될경우 에지(u,v)는 A에 대해서 안전하다(safe)고 한다.- Generic MST 알고리즘1. 처음에는 A는 공집합이다.2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.3. 에지의 개수가 n-1개가 ..