Chapter8 Greedy Algorithm 탐욕 알고리즘

1. 수업 시간표 짜기 문제 학교에서 되도록 많은 수업을 듣고 싶어한다고 가정하자.

1. 가장 빨리 끝나는 과목을 고름. 이과목이 처음으로 신청해야할 과목.
2. 이제 첫 번째 과목이 끝난후에 시작하는 과목중 가장 빨리 끝나는 과목을 고름.
3. 2번을 반복하면 정답을 얻을 수 있다.

• 탐욕 알고리즘의 장점은 간단하다는 것이다.
• 각 단계에서 국소 최적해를 찾음 으로써 최종적으로는 전역 최적해를 구하게 된다.
• 탐욕 알고리즘이 항상 성공하는 것은 아니다. 하지만 간단해서 구현하기 좋다.

1. 배낭채우기 문제 35파운드만 담을수 있는 배낭이 있다. 배낭에 넣을 물건의 가겨의 합을 최대한 크게 하고 싶다.

1. 가방에 들어갈 수 있는 것중에서 가장 비싼 물건을 고릅니다.
2. 그 다음으로 가방에 들어갈 수 이는 물건중 가장 비싼것을 고름
3. 2 번 반복. 하지만 이번엔 제대로 동작 하지 않는다.
4. 이처럼 올바른 답을 내놓지 못했지만 정답에 상당히 가까운 답 이기도 함.

꽤 괜찮은 정도로만 문제를 풀어도 되는 상황이면 탐욕 알고리즘이 좋다. 보통 정답에 근사한 답을 내 주기 때문이다.

1. 집합 커버링 문제 미국 50개의 주에 있는 모든 사람에게 라디오 쇼를 들려주고 싶다. 전국의 모든 사람들이 최소한 한 번은 라디오 쇼를 들을 수 있도록 하려면 어떤 방속국을 방문해야 할지 계산 해야 함. 또 방속국을 방문하여 한 번 쇼를 하는데 돈이 들기 때문에 최대한 적은 수의 방송국을 돌아야함.

각 방송국마다 겹치거나 커버할 수 있는 지역이 다름.

1. 가능한 모든 방송국의 부분 집합을 나열. 이것을 멱집합 이라고 함. 가능 한 부분 집합의 수는 2ⁿ
2. 이 부분 집합 중에 50 개 주 전체를 커버할 수 있으면서 가장 원소의 수가 적은 부분 집합을 고름.

문제는 부분 집합을 계산하는데 시간이 많이 걸림. 부분 집합의 수가 2ⁿ이기 때문에 O(2ⁿ)시간이 걸림. 이 문제에 대해 충분히 빠른 속도를 가진 알고리즘은 존재 하지 않는다. 이럴때 탐욕 알고리즘을 사용하면 된다. 다은 알고리즘은 정답과 거의 비슷한 답을 유추 한다.

1. 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고름. 이미 방속 되고 있는 지역이 일부 포함되어 있어도 상관없다.
2. 모든 주에 방송이 될 떄까지 선택을 반복

이것을 근사 알고리즘 이라고 함. 정확한 답을 계산하는데 시간이 너무 많이 걸린다면 근사사 알고리즘을 사용할 수 있다. 근사알고리즘의 성능은 두가지로 판단

• 얼마나 빠른다
• 최적해에 얼마나 가까운가 이 경우 탐욕 알고리즘의 실행 속도는 O(n²). 여기서 n은 방송국 수

코드 방송하고자 하는 주의 목록을 만듬

# 배열 넣으면 집합이 된다.
# set을 사용하여 중복된 원소를 가지지 않는다.
states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])

그리고 선택된 방송국의 목록도 필요. 이 목록을 저장하는데는 해시 테이블을 사용.

# 방송국 목록
stations = dict()
stations["kone"] = set(['id', 'nv', 'ut'])
stations["ktwo"] = set(['wa', 'id', 'mt'])
stations["kthree"] = set(['or', 'nv', 'ca'])
stations["kfour"] = set(['nv', 'ut'])
stations["kfive"] = set(['ca', 'az'])

방문할 방송국의 목록을 저장할 집합이 필요

# 방문한 방송국의 목록을 저장할 집합
final_stations = set()

모든 방송국을 하나씩 보면서 아직 방송이 되지 않는 주 중에서 가장 많은 주를 커버하고 있는 방송국을 고름 이 방송국을 best_station 이라고 함

# 아직 방송이 되지 않는 주 중에서 가장 많은 주를 커버하고 있는 방송국
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

• 합집합은 두 집합을 합친다.
• 교집합은 두 집합에 모두 초함되어 있는 원소들의 집합을 말함.
• 차집합은 어떤 집합에서 다른 집합에 포함되어 있는 원소를 뺀 나머지 원소의 집합을 말함.

fruits = set(['avocado', 'tomato', 'banana'])
vegetables = set(['beets', 'carrots', 'tomato'])
fruite | vegetables # 이것은 합집합
# >> set(['avocado', 'beets', 'carrots', 'tomato', 'banana'])
fruits & vegetables # 이것은 교집합
# >> set(['tomato'])
fruits - vegetables # 이것은 차집합
# >> set(['avocado', 'banana'])
vegetables - fruits # 이것도 차집합
# >> set(['beets', 'carrots'])

• 집합은 리스트와 비슷하지만 중복을 허용하지 않는다.
• 집합에서는 합집합, 교집합, 차집합과 같은 재미있는 연산을 할 수 있다.

states_needed와 states_for_station에 모두 포함된 주의 집합. 아직 방송되지 않는 주 중에서 현재 고려하고 있는 방송국이 커버하는 주의 집합.

covered = states_needed & states_for_station

현재의 bset_station보다 더 많은 주를 커버 하는지 확인하고 그렇다면 해당 방송국이 새로운 bset_station이며 방송국이 커버 하는 주의 집합을 갱신한다.

if len(covered) > len(states_covered):
    best_station = station
    states_covered = covered

그리고 해당 방송국에서 커버하는 주는 이제 더이상 고려할 필요가 없으므로 집합에서 제외

states_needed -= states_covered

최선의 선택을 받은 bset_station을 순회할 방송국 목록에 추가한다.

final_stations.add(best_station)

전체 코드

# 배열 넣으면 집합이 된다.
# set을 사용하여 중복된 원소를 가지지 않는다.
states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])

# 방송국 목록
stations = dict()
stations["kone"] = set(['id', 'nv', 'ut'])
stations["ktwo"] = set(['wa', 'id', 'mt'])
stations["kthree"] = set(['or', 'nv', 'ca'])
stations["kfour"] = set(['nv', 'ut'])
stations["kfive"] = set(['ca', 'az'])

# 방문한 방송국의 목록을 저장할 집합
final_stations = set()

# 모든 방송국을 다 돌때 까지
while states_needed:
    # 아직 방송이 되지 않는 주 중에서 가장 많은 주를 커버하고 있는 방송국
    best_station = None
    # 아직 방송이  되지 않은 주 중에서 해당 방송국이 커버하는 주의 집합
    states_covered = set()

    # 모든 방송국 중에 어떤 것이 최선의 선택인지 알아봄.
    for station, states_for_station in stations.items():
        # 교집합
        # states_needed와 states_for_station에 모둠 포함된 주의 집합.
        # 아직 방송되지 않는 주 중에서 현재 고려하고 있는 방송국이 커버하는 주의 집합.
        covered = states_needed & states_for_station
        # 현재의 bset_station보다 더 많은 주를 커버 하는지 확인
        if len(covered) > len(states_covered):
            # 그렇다면 이 방송국이 새로운 best_station
            best_station = station
            # 방송국이 커버 하는 주의 집합을 갱신
            states_covered = covered

    # 이 방송국에서 커버하는 주는 이제 더이상 고려할 필요가 없다.
    states_needed -= states_covered
    # 최선의 선택을 받은 방송국을 목록에 추가
    final_stations.add(best_station)

print(final_stations)
# >> set(['ktwo', 'kthree', 'kone', 'kfive'])

1. NP-완전문제 집합 커버링문제를 풀기 위해서는 가능한 모든 집합을 계산해야 함 외판원 문제는 다섯 개의 서로 다른 도시를 방문 해야 함. 외판원은 다섯 개의 도시를 모두 지나는 최단 경로를 알아내고자 함.그러기 위해서는 우선 가능한 모든 경로를 계산해야 함.

단계 별로 풀어 보는 외판원 문제

작은 것부터 시작. 우선 도시가 두개 밖에 없다고 가정. 그리고 최적 경로와 출발점을 계산하는 것도 외판원 문제에서 풀어야 할 계산에 포함될 수 있다. 도시가 두개 인경우 = 가능한 경로는 두개

도시가 세개 인 경우

전체 6개의 경로가 있고, 각각의 도시에서출발하는 방법은 2가지 3개의 도시 = 6개의 경로

도시가 네개 인 경우

한점에서 출발하여 도착할 수 있는 경로는 6개 도시가 4개이니까 24개 가 된다.

해당 패턴은 팩토리얼 함수로 동작한다. 외판원 문제와 집합 커버링 문제는 공통점이 있다. 모든 가능한 경우를 다 따져서 최단최소를 구해야 한다는 것. 이런 문제는 NP-완전 문제라고 함.

근사화 외판원 문제에 대해 좋은 근사 알고리즘은 없을까? 짧은 거리를 찾는 방법은 일단 아무도시나 고르고 아직 방문하지 않은 가장 가까운 도시를 다음 방문지로 선택 그렇게 계속 가다보면 최단거리는 아니겠지만 짧은 거리이기는 하다.

NP-완전 문제는 어렵기로 유명하다. 많은 똑똑한 사람들이 이 문제를 빠르게 해결할 수 있는 알고리즘을 만드는 것은 불가능 하다고 생각함.

어떤 문제가 NP-완전 문제인지 알 수 있는 방법은?

NP-완전문제는 어디에나 나타난다. 우리가 풀고자 하는 문제가 NP-완전 문제 라는것을 알아낸다는 것은 좋은 일이다. 그 시점에서 문제를 완벽하게 풀려는 노력은 멈추고, 대신 근사 알고리즘을 써서 풀수 있으니까. 하지만 어떤 문제가 NP-완전 인지 아는 것은 어려운 일. 보통 쉽게 풀리는 문제와 NP-완전 문제 사이에는 조근만 차이 밖에 없다. 하지만 우리가 풀려고 하는 문제가 NP-완전 문제인지 아닌지 알 수 있는 쉬운 방법은 존재 하지 않는다 다만 몇가지 참고 사항은 있다.

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

이번에 배운내용

• 탐욕 알고리즘은 전역 최적화를 목표로 하지만, 실제로는 국소 최적화를 한다.
• NP-완전 문제는 빠른 해답이 알려지지 않았다.
• 만약 NP-완전 문제가 주어지면 근사 알고리즘을 쓰는 것이 최선
• 탐욕 알고리즘은 작성하기도 쉽고 빠르기 떄문에 좋은 근사 알고리즘이 될 수 있다.