알고리즘(탐욕 알고리즘)

Hello Coding 그림으로 개념을 이해하는 알고리즘 책 정리

탐욕 알고리즘

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다. - 위키백과 -

매트로이드

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다. 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

근사 알고리즘

근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 근사해를 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다. - 위키백과 -

탐욕 알고리즘은 각각의 단계에서 최적의 수를 찾아내면 된다. 각 단계에서 국소 최적해를 찾음으로는 전역 최적해를 구하게 된다고 한다. 그러나 탐욕 알고리즘이 항상 성공하는 것은 아니다.

수업 시간표 짜기 문제

배낭 채우기 문제

집합 커버링 문제

전국의 모든 사람들이 최소한 한 번은 쇼를 들을 수 있도록 하려면 어떤 방속국을 방문해야 할지 계산한다. 또 방송국을 방문하여 한 번 쇼를 하는데 돈을 들기 때문에 최대한 적은 수의 방송국을 돌아야 한다.
조건
1. 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국 선택. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관 없다.
2. 모든 주에 방송이 될 때까지 선택을 반복한다.

근사 알고리즘

계산이 오래 걸리면 근사 알고리즘을 사용한다. 단순해서 실행 속도가 빠르다.
근사 알고리즘의 성능은 얼마나 빠른가혹은 최적해에 얼마나 가까운가로 판단한다.

코드

# 방송하고자 하는 주의 목록
states_needed = set(["mt","wa","or","id","nv","ut","ca","az"])

# 선택된 방송국 목록
stations = {}
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 in stations.items():
        print(f'states_covered {states_covered}')

        # 방송되지 않은 주 중에서 현재 고려하고 있는 방송국이 커버하는 주의 집합
        covered = states_needed & states
        print(covered)

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

        print(best_station)

    # 방송국에서 커버하는 주는 이제 더이상 필요 없으므로 갱신
    states_needed -= states_covered
    final_stations.add(best_station)

print(final_stations)

정확한 알고리즘 O(n!), 그에 비해 탐욕 알고리즘 O(n^2)

집합 자료형

집합(set) 타입은 리스트와 비슷하지만 각 원소가 한번씩만 나타난다. 즉 중복된 원소를 가지지 않는다. 또한 순서가 없다.
교집합, 합집합, 차집합으로 활용 할 수 있다.

fruits = set(["avocado","tomato","banana"])
vegetables = set(["beets","carrots","tomato"])

# 합집합
>> fruits | vegetables
>> {'avocado', 'banana', 'beets', 'carrots', 'tomato'}

# 교집합
>> fruits & vegetables
>> {'tomato'}

# 차집합
>> fruits - vegetables
>> {'avocado', 'banana'}

NP - 완전 문제

NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. - 위키 백과 -

NP-완전문제 판별법

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

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.