탐욕 알고리즘 (Greedy algorithm)

각각의 단계에서 최적의 수를 찾아내기만 하면 되기 때문에 간단하다. 기술적 용어로는 각 단계에서 국소 최적해(locally optimal solution)을 찾음으로써 최종적으로는 전역 최적해(globally optimal solution)을 구하게 된다고 한다. 항상 성공하는 것은 아니다.

전역 최적화를 목표로 하지만, 실제로는 국소 최적화를 한다.

수업 시간표 짜기 문제 (classroom scheduling problem)

학교에서 되도록 많은 수업을 듣고 싶어한다고 가정할시

가장 빨리 끝나는 과목을 고른다. 이 과목이 처음으로 신청해야 할 과목이다.
첫 번째 과목이 끝난 후에 시작하는 과목을 고르는데, 마찬가지로 가장 빨리 끝나는 과목을 고른다.
반복한다.

근사 알고리즘(approximation algorithm)

배낭 채우기 문제

35파운드의 무게까지 담을 수 있는 배낭에 넣을 물건의 가격의 합을 최대한 크게 하고자 하는 경우, 탐욕 알고리즘 적용시 재대로 동작하지 않는다.

가방에 들어갈 수 있는 것 중에서 가장 비싼 물건을 고른다.
그 다음으로 비싼 물건을 고른다.
반복한다.

배낭에 들어가는 물건의 무게 때문에 최고의 답이 나오지 않을 수도 있다. 하지만 정답에 상당히 가까운 답을 줄 수 있다.

집합 커버링 문제 (set-covering problem)

하나의 방송국을 통해 청취할 수 있는 지역(cover 지역)이 한정되어 있을 때 최대한 적은 수로 모든 지역을 커버하고자 하는 경우

가능한 모든 방송국의 부분 집합을 나열한다. 이를 멱집합(power set)이라고 한다. 가능한 부분집합의 수는 2^n개이다.
이 부분 집합 중에 50개 주 전체를 커버할 수 있으면서 가장 원소의 수가 적은 부분 집합을 고른다.

모두 가능한 부분 집합을 계산하는 데 시간이 많이 걸리는 문제가 있다. 부분 집합의 수가 2^n개이기 때문에 O(2^n)시간이 걸린다. 이 문제에 대해 충분히 빠른 속도를 가진 알고리즘은 존재하지 않는다. 이런 경우 탐욕 알고리즘을 사용해 거의 정답과 비슷한 답을 유추한다.

아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관없다.
모두 지역에 방송이 될때까지 반복한다. 이 경우 탐욕 알고리즘의 실행 속도는 O(n^2)시간이다. (n = 방송국 수)

이를 근사 알고리즘(approximation algorithm)이라고 한다.


## 방송하고자 하는 지역 목록
states_needed = set(["mt","wa","or","id","nv","ut","ca","az"])  # 배열을 넣으면 집합이 된다. (파이썬에서 집합set타입 사용시 중복된 원소를 가지지 않는다.)

## 방송국 목록 - 해시 테이블 사용
stations = {}
stations["k1"] = set(["id", "nv", "ut"])    # 키=방송국 명, 값=지역목록
stations["k2"] = set(["wa", "id", "mt"])
stations["k3"] = set(["or", "nv", "ca"])
stations["k4"] = set(["nv", "ut"])
stations["k5"] = set(["ca", "az"])

## 방문할 방송국 목록 집합
final_stations = set()

while states_needed :
    best_station = None # 아직 방송이 되지 않은 주 중에서 가장 많은 주를 커버하는 방송국
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station # 집합연산(교집합)
        if len(covered) > len(states_covered) :
            best_station = station
            states_covered = covered

    states_needed -= states_covered
    final_stations.add(best_station)


print final_stations

근사 알고리즘 성능 판단 기준

얼마나 빠른가
최적해에 얼마나 가까운가

NP-완전 문제

집합 커버링 문제를 풀기 위해서는 가능한 모든 집합을 계산해야 한다. 외판원 문제와 집합 커버링 문제처럼 모든 가능한 경우를 다 따져서 최단/최소를 구해야 하는 경우 NP-완전 문제(NP-complete problem) 이라고 한다.

NP-완전 문제인가를 구분할 수 있는 쉬운 방법은 존재하지 않지만 아래를 참고할 수 있다.

항목이 적을 때는 알고리즘이 빠른데, 늘어나면 급격하게 느려지는 경우.
“X의 모든 조합"이라고 하면 보통 NP-완전 문제이다.
더 작은 하위 문제로 변환할 수가 없어서 X의 가능한 모든 버전을 계산해야 하는 경우.
문제가 수열(외판원 문제와 같은)을 포함하고 풀기가 어려운 경우.
문제에 집합(라디오 방송국 처럼)이 있고 풀기가 어려운 경우.
문제를 집합 커버링 문제나 외판원 문제로 재정의할 수 있다면, 명백하게 NP-완전 문제이다.

NP-완전 문제가 주어진다면 근사 알고리즘을 쓰는 것이 최선이다.
탐욕 알고리즘은 작성하기도 쉽고 빠르기 때문에 좋은 근사 알고리즘이 될 수 있다.

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘

알고리즘 탐욕