DAA-욕심 많은 방법

모든 알고리즘 접근 방식 중에서 가장 간단하고 직접적인 접근 방식은 Greedy 방법입니다. 이 접근 방식에서는 미래의 현재 결정의 영향에 대해 걱정하지 않고 현재 사용 가능한 정보를 기반으로 결정을 내립니다.

Greedy 알고리즘은 부분적으로 솔루션을 구축하여 즉각적인 이점을 제공하는 방식으로 다음 부분을 선택합니다. 이 접근 방식은 이전에 취한 선택을 결코 재고하지 않습니다. 이 접근 방식은 주로 최적화 문제를 해결하는 데 사용됩니다. Greedy 메서드는 구현하기 쉽고 대부분의 경우 매우 효율적입니다. 따라서 Greedy 알고리즘은 글로벌 최적 솔루션을 찾기 위해 각 단계에서 로컬 최적 선택을 따르는 휴리스틱 기반 알고리즘 패러다임이라고 말할 수 있습니다.

많은 문제에서 합리적인 시간에 근사 (최적에 가까운) 솔루션을 제공하지만 최적의 솔루션을 생성하지 않습니다.

Greedy 알고리즘의 구성 요소

Greedy 알고리즘에는 다음과 같은 다섯 가지 구성 요소가 있습니다.

• A candidate set −이 세트에서 솔루션이 생성됩니다.

• A selection function − 솔루션에 추가 할 최적의 후보를 선택하는 데 사용됩니다.

• A feasibility function − 후보자가 솔루션에 기여할 수 있는지 여부를 결정하는 데 사용됩니다.

• An objective function − 솔루션 또는 부분 솔루션에 값을 할당하는 데 사용됩니다.

• A solution function − 완전한 솔루션에 도달했는지 여부를 나타내는 데 사용됩니다.

적용 분야

탐욕적인 접근 방식은 다음과 같은 많은 문제를 해결하는 데 사용됩니다.

• Dijkstra의 알고리즘을 사용하여 두 정점 사이의 최단 경로 찾기.

• Prim의 / Kruskal의 알고리즘 등을 사용하여 그래프에서 최소 스패닝 트리 찾기

욕심 많은 접근이 실패하는 곳

많은 문제에서 Greedy 알고리즘은 최적의 솔루션을 찾지 못하고 최악의 솔루션을 생성 할 수 있습니다. Traveling Salesman 및 Knapsack과 같은 문제는이 방법으로 해결할 수 없습니다.