탐욕 알고리즘 (Greedy algorithm)

 

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

일반적으로 욕심 많은 알고리즘에는 5 가지 구성 요소가 있습니다.

1. 솔루션이 생성되는 후보 세트

2.솔루션에 추가 할 최적의 후보를 선택하는 선택 기능

3.후보자가 솔루션에 기여할 수 있는지 여부를 결정하는 데 사용되는 실행 가능성 함수

4. 솔루션 또는 부분 솔루션에 값을 할당하는 목적 함수

5. 완전한 솔루션을 발견 한시기를 나타내는 솔루션 함수

탐욕스러운 알고리즘은 일부 수학적 문제 에 대해 좋은 솔루션을 생성 하지만 다른 문제 에 대해서는 그렇지 않습니다. 작동하는 대부분의 문제에는 두 가지 속성이 있습니다.

 

Greedy 알고리즘은 조합 최적화 및 이론적 컴퓨터 과학 에서 오랜 연구 역사를 가지고 있습니다 . 탐욕 스러운 휴리스틱은 많은 문제에 대해 차선의 결과를 생성하는 것으로 알려져 있습니다. 따라서 자연스러운 질문은 다음과 같습니다.

● 탐욕 알고리즘은 어떤 문제에 대해 최적으로 수행됩니까?

● 탐욕 알고리즘은 어떤 문제에 대해 최적의 솔루션을 보장합니까?

● 탐욕 알고리즘 이 최적의 솔루션을 생성 하지 못하도록 보장하는 문제는 무엇입니까?

 

matroids 와 같은 일반적인 문제 클래스 뿐만 아니라 set cover 와 같은 특정 문제에 대해 이러한 질문에 답하는 많은 문헌이 존재합니다 .

최대 합계에 도달하기 위해 각 단계에서 욕심 많은 알고리즘은 최적의 즉각적인 선택으로 보이는 것을 선택하므로 두 번째 단계에서 3 대신 12를 선택하고 다음을 포함하는 최상의 솔루션에 도달하지 않습니다.

 

Greedy 알고리즘은 대부분 (항상 그런 것은 아님) 일반적으로 모든 데이터에 대해 철저하게 작동하지 않기 때문에 전역 적으로 최적의 솔루션을 찾지 못합니다. 특정 선택을 너무 일찍 약속하여 나중에 최상의 전체 솔루션을 찾지 못할 수 있습니다. 예를 들어, 그래프 채색 문제 및 기타 모든 NP- 완전 문제에 대해 알려진 모든 탐욕스러운 채색 알고리즘은 지속적으로 최적의 솔루션을 찾지 못합니다. 그럼에도 불구하고 그들은 빠르게 생각하고 종종 최적의 근사치를 제공하기 때문에 유용합니다.

탐욕 알고리즘이 주어진 문제 클래스에 대해 전역 최적을 산출하는 것으로 입증 될 수 있다면, 동적 프로그래밍 과 같은 다른 최적화 방법보다 빠르기 때문에 일반적으로 선택 방법이됩니다 . 이러한 탐욕스러운 알고리즘의 예로는 Kruskal의 알고리즘 과 최소 스패닝 트리 를 찾는 Prim의 알고리즘 , 최적의 Huffman 트리 를 찾는 알고리즘이 있습니다.

Greedy 알고리즘은 네트워크 라우팅 에도 나타납니다 . 탐욕스러운 라우팅을 사용하여 메시지는 목적지에 "가장 가까운"인접 노드로 전달됩니다. 노드 위치의 개념 (따라서 "가까움")은 애드혹 네트워크에서 사용하는 지리적 라우팅 에서와 같이 물리적 위치에 의해 결정될 수 있습니다 . 위치는 또한 작은 세계 라우팅 및 분산 해시 테이블에서 와 같이 완전히 인공적인 구성 일 수 있습니다 .

● 활동 선택 문제는 목표가 서로 충돌하지 않는 최대 활동 수를 선택하는 것이, 이 문제 클래스의 특징입니다.

● 매킨토시 컴퓨터 게임 Crystal Quest에서 목표는 여행하는 세일즈맨 문제와 유사한 방식으로 크리스탈을 수집하는 것입니다. 게임에는 욕심 많은 알고리즘을 사용하여 모든 크리스탈로 이동하는 데모 모드가 있습니다. 인공 지능은 장애물을 고려하지 않으므로 데모 모드는 종종 빠르게 종료됩니다.

● 매칭 추구는 신호 근사에 적용되는 탐욕 알고리즘의 예입니다.

● 탐욕스러운 알고리즘은 주어진 삼각형 내에서 원의 총 면적을 최대화하는 3 개의 분리 된 원을 찾는 Malfatti의 문제 에 대한 최적의 솔루션을 찾습니다. 동일한 탐욕 알고리즘이 모든 원에 대해 최적이라고 추측됩니다.

● 탐욕 알고리즘은 최적의 솔루션을 찾는 Huffman 코딩 중에 Huffman 트리를 구성하는 데 사용됩니다 .

● 의사 결정 트리 학습에서는 일반적으로 탐욕스러운 알고리즘이 사용되지만 최적의 솔루션을 찾을 수 있다고 보장 할 수는 없습니다.

● 이러한 알고리즘 중 하나는 의사 결정 트리 구성을위한 ID3 알고리즘 입니다.

● Dijkstra의 알고리즘 및 관련 A * 검색 알고리즘 은 그래프 검색 및 최단 경로 찾기를 위한 검증 가능한 최적의 탐욕스러운 알고리즘입니다 .

● A * 검색은 조건부로 최적이며 경로 비용을 과대 평가하지 않는 " 허용 가능한 휴리스틱 "이 필요합니다 .

● Kruskal의 알고리즘 과 Prim의 알고리즘 은 주어진 연결된 그래프 의 최소 스패닝 트리 를 구성하기위한 탐욕스러운 알고리즘입니다 . 일반적으로 고유하지 않을 수있는 최적의 솔루션을 항상 찾습니다.

 

출처 : 위키백과