탐욕 알고리즘: 지금의 최선이 전체의 최선이 되는 조건
탐욕 알고리즘은 현재 단계에서 가장 좋아 보이는 선택을 하고 그 선택을 되돌리지 않는 방식이다. 구현이 간단하고 빠를 수 있지만 국소적으로 좋은 선택이 전체 최적을 보장하는 것은 아니다. 선택 규칙과 그 규칙의 안전성을 함께 증명해야 한다.
이 예시는 끝을 포함하지 않는 구간이며 종료 시각이 빠른 활동부터 선택한다.
활동 선택에서 종료 시각을 고르는 이유
한 자원에서 시간이 겹치지 않는 활동을 가장 많이 수행하려면 종료가 가장 빠른 활동을 먼저 고르는 규칙이 맞다. 빨리 시작하는 활동이나 길이가 짧은 활동이라는 다른 규칙은 항상 맞지 않는다.
def choose_activities(activities):
# Each activity is (start_time, end_time).
ordered = sorted(activities, key=lambda activity: activity[1])
selected = []
previous_end = float("-inf")
for start_time, end_time in ordered:
if start_time >= previous_end:
selected.append((start_time, end_time))
previous_end = end_time
return selected
코드는 끝나는 시각과 다음 시작 시각이 같으면 겹치지 않는다고 정의한다. 구간의 끝을 포함하는 다른 정의라면 조건을 조정해야 한다. 정렬 O(n log n), 순회 O(n)이므로 전체 O(n log n)이다.
최적해의 첫 활동이 가장 빨리 끝나는 활동이 아니라고 하자. 그것을 가장 빠른 종료 활동으로 바꿔도 뒤 활동들은 여전히 실행 가능하다. 개수도 줄지 않는다. 따라서 그 탐욕 선택을 포함하는 최적해가 존재한다. 남은 활동에도 같은 논리를 적용하는 것이 교환 논증이다.
자연스러운 규칙도 반례가 있다
동전 종류가 1,3,4이고 금액 6을 만들 때 큰 동전부터 고르면 4+1+1로 세 개다. 3+3은 두 개라 더 좋다. 흔한 화폐 체계에서 잘 작동한 규칙을 임의의 동전 집합에 일반화할 수 없다.
가중 활동 선택도 다르다. 최대 활동 수가 아니라 총보상이 목표라면 짧은 활동 하나가 긴 고보상 활동을 막을 수 있다. 같은 입력 모양이라도 목적 함수가 달라지면 탐욕의 증명이 깨진다.
탐욕 선택 성질은 첫 국소 선택을 포함하는 최적해가 있음을 뜻하고, 최적 부분 구조는 그 선택 뒤 남은 문제도 최적으로 해결해야 함을 뜻한다. 둘 중 후자만 있어도 탐욕이 가능한 것은 아니다. 동적 계획법은 여러 선택을 비교하며 최적 부분 구조를 활용할 수 있다.
최소 신장 트리의 컷 성질이나 허프만 코드의 결합 규칙도 안전한 탐욕 선택의 근거를 제공한다. “일단 가장 작은 것을 고른다”는 설명만으로는 증명이 아니다. 반례를 찾고, 선택을 다른 최적해와 교환해도 손해가 없다는 구조를 확인하는 것이 핵심이다.
작은 입력을 전수 검사해 탐욕 결과와 최적값을 비교하면 반례 발견에 도움이 된다. 다만 반례를 찾지 못했다는 사실이 모든 크기의 정확성 증명은 아니다.