탐욕알고리즘 기초개념

2019-01-31

탐욕알고리즘 기초개념 요약 및 Python 프로그래밍 구현연습

ㅇ 학습 시 참고한 도서정보

제목 : Hello Coding 그림으로 개념을 이해하는 알고리즘
저자&출판사 : 아디트야 바르가바 지음, 김도형 옮김 / 한빛미디어

탐욕알고리즘

각각의 단계에서 최적의 수를 찾는 알고리즘
각 단계에서 국소최적회(local optimal solution)을 찾음으로써 최종적으로는 전역 최적해(globally optional solution)을 구하는 알고리즘

# 예시

수업시간표 짜기

가장 빨리 끝나는 과목을 고른다.
탐욕알고리즘으로 최적의 해를 구할 수 있다.

배낭 채우기 문제

도둑의 배낭이 35kg까지 담을 수 있다
훔친 물건이 세개가 있다.

1 ) 라디오 : 30kg, 300만원

2 ) 노트북 : 20kg, 200만원

3 ) 기타 : 15kg, 150만원

탐욕알고리즘에 의하면 가방에 들어갈 수 있는 것중에서 가장 비싼 물건을 고르면 된다.
배낭 채우기 문제에서는 탐욕알고리즘이 제대로 작동하지 않는다.
- 라디오가 가장 비싸기 때문에 라디오를 가방에 넣게 되면 다른 것은 못넣게 되는데 기타와 라디오를 넣게 되면 총 가치가 350만원으로 라디오 하나 훔치는 것 보다 가치있게 된다.

” 완벽한 정답을 찾는 것보다 근사하게 문제를 풀어도 되는 상황이 있기 때문에 탐욕알고리즘이 가치가 있는것이다.
예를 들어 다음에 나올 집합 커버링 문제처럼..”

집합커버링 문제

50개 주 전체를 커버하는 가장 적은 수의 방송국의 집합은 어떻게 구하면 될까
가능한 모든 방송국의 부분집합을 나열하게 되면 가능 한 부분집합의 수는 \(\ 2^n\)개이다.
조사할 n이 작다면 상관이 없는데 점점 커지면 커질 수록 엄청나게 시간이 많이 걸리게 될 것이다.
이럴때 탐욕 알고리즘을 쓰면 매우 유용하다. 충분히 빠른속도로 정답과 거의 비슷한 답을 유추하기 때문이다.

1 ) 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국으로 고른다.

2 ) 모든 주에 방송이 될때까지 반복한다.

위와같은 알고리즘을 근사알고리즘이라고 한다. 정확한 답을 계산하는데 시간이 너무 많이 걸릴때 사용할 수 있다.
근사알고리즘의 성능판단.

1 ) 얼마나 빠른가

2 ) 최적해에 얼마나 가까운가

근사알고리즘 구현 (라디오 방송국 커버하기)
최소한의 라디오 방송국을 방문하는데 전국의 모든 지역을 한번은 커버해야한다.

1 ) states_needed는 전국의 지역 모음

2 ) stations는 방송국들의 모임 그리고 그들의 각각의 집합은 그들이 커버하는 지역

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():
        covered = states_needed & states
        
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
            
    states_needed -= states_covered
    final_stations.add(best_station)

final_stations

{'kfive', 'kone', 'kthree', 'ktwo'}

탐욕 알고리즘은 전역 최적화를 목표로하지만 실제로는 국소 최적화를 한다.
NP-완전 문제는 빠른 해답이 알려지지 않았다.
NP-완전문제 : 모든 가능한 경우를 다 따져서 최단/최소 시간을 구해야하는 문제

ex) 외판원문제, 집합 커버링

NP-완전문제인지 아닌지 판단 시 참고사항

1 ) 항목이 적을때는 알고리즘이 빠른데, 항목이 늘어나면 갑자기 느려질때

2 ) X의 모든조합 이라고 하면 보통 NP-완전문제다.

3 ) 더 작은 하위 문제로 변환할 수 없어서 X의 가능한 모든 버전을 계산해야 한다면 NP완전문제일 것이다.

4 ) 문제가 수열을 포함하고 풀기가 어려우면 NP 완전문제 일 수도 있다.

5 ) 먄약 문제에 집합이 있고 풀기 어려우면 NP 완전문제 일 수도 있다.

6 ) 문제를 집합 커버링 문제나 외판원 문제로 재정의 할 수 있다면 명백하게 NP완전문제이다.

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

 다익스트라 알고리즘 기초개념 해시테이블 기초개념 