5. Greedy algorithms

탐욕적 알고리즘에 대해 알아보자.

5.1. Minimum spanning trees

최소 신장 트리를 구하려면 어떻게 할까? 우선, 순환 간선을 없애는 것은 그래프를 비연결로 만들지 않는다.

5.1.1. A greedy approach

순환을 만들지 않는 가장 가중치가 작은 간선을 추가하면 된다.

5.1.2. The cut property

최소 신장 트리의 일부분 X가 있을 때 X가 S, V – S를 가로지르지 않는 정점들 S를 택하고 이 분할을 가로지르는 간선 중 가장 최소의 것 e를 택하면 X ∪ {e}는 최소 신장 트리의 일부가 된다.

5.1.3. Kruskal’s algorithm

위로부터 크루스칼의 알고리즘을 정의할 수 있다. 간선을 가중치 순으로 정렬한 뒤 각 간선을 증가하는 순서로 놓고 병합 찾기로 간선을 추가하면 된다.

5.1.4. A data structure for disjoint sets

병합 찾기는 사실상 선형 시간이다.

5.1.5. Prim’s algorithm

프림의 알고리즘도 정의할 수 있다. 지금까지 만든 최소 신장 트리를 X라 할 때 X가 S, V – S를 가로지르지 않는 정점들 S를 택하고 이 분할을 가로지르는 간선 중 가장 최소의 것 e를 택해 추가하면 된다.

5.2. Huffman encoding

문자열 T를 이진 문자열로 인코딩하는 데 허프만 인코딩이 쓰인다. 이도 탐욕적 알고리즘으로 구현된다.

5.3.Horn formulas

SAT 문제에 대한 근사를 호른의 식으로 근사할 수 있다. 이 때 탐욕적 근사 알고리즘이 존재한다.

5.4. Set cover

집합 덮개 문제는 NP-난해이다. 탐욕적 근사 알고리즘이 존재한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중