탐욕 알고리즘은 각 단계에서 정한 기준에 가장 유리한 선택을 하며 해를 구성하는 방법이다.
원리
국소적으로 좋은 선택이 전체 최적해로 이어지는 문제 구조가 필요하다. 교환 논증이나 안전한 선택의 성질로 선택 규칙을 정당화한다.
예시
겹치지 않는 활동을 가장 많이 고르는 문제에서는 끝나는 시간이 가장 이른 활동부터 선택하는 전략이 성립한다. 단순히 가장 짧은 활동부터 고르는 규칙과는 다르다.
주의할 점
그럴듯한 규칙만으로 최적성을 보장할 수 없다. 동전 단위가 1, 3, 4일 때 6을 큰 동전부터 만들면 4+1+1이지만 최적해는 3+3이다.