집합 커버링 문제(set-covering problem)
근사 알고리즘
미국 50개 주에 방송을 하고 싶다. 이를 위해서는 방송국을 찾아가야 하는데, 이 방송국들은 각각 커버하는 주가 다르다. 방송국에 찾아가는 데는 비용이 드므로 방송국을 가장 적게 찾아가면서도 50개 주를 다 포함하게끔 하고 싶다. 이를 해결하기 위해 탐욕 알고리즘을 사용한다. (거의 정답에 가까운 답을 유추)
- 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 관계 없다.
- 모든 주에 방송이 될 때까지 반복한다.
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 방송하고자 하는 주의 목록
best_station = None # 가장 많은 주를 커버하는 방송국
states_covered = set() # 아직 방송되지 않은 주 중에서 해당 방송국이 커버하는 주의 집합(set을 사용)
for station, states_for_station in stations.items():
covered = states_needed & states_for_station # 집합의 교집합 syntax
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
- covered는 아직 방송되지 않은 주 중에서 현재 고려하고 있는 방송국이 커버하는 주의 집합.
- states_covered는 현재의 best_station이 커버하는 주
final_stations.add(best_station) # for문이 끝나면 best_station을 방송국 목록에 추가
states_needed -= states_covered # 커버한 주는 고려 집합에서 제외
- states_needed가 빌 때까지 반복한다.
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)
>>> print final_stations
외판원 문제
미국의 n개 주를 방문하여 판매를 해야하는 외판원이 있다. n개 주를 모두 거치되, 최단 경로로 이동하려면 검토해야 할 경로는 총 몇 개인가??
1개 주 -> 1개의 경로
2개 주 -> 출발 가능한 도시는 2개 * 각 도시에서 출발하는 1개의 경로 = 전체 2개의 경로
3개 주 -> 출발 가능한 도시는 3개 * 2개의 경로 = 전체 6개의 경로
4개 주 -> 출발 가능한 도시는 4개 * 6개의 경로 = 전체 24개의 경로
즉 주가 n개이면 경로는 n!개이다. n이 커질 수록 n!은 매우 빠르게 증가한다.
외판원 문제와 집합 커버링 문제의 공통점은 최단/최소를 구하기 위해 모든 가능한 경우의 수를 따져야 한다는 것이다. 이를 NP-완전 문제(NP-complete problem)이라고 한다.
NP-완전 문제
어떤 문제가 NP-완전 문제인지 아는 것은 중요하다. 그러면 모든 수를 검토하는 대신 근사 알고리즘을 써서 빠르게 정답에 가까운 답을 유추할 수 있을 것이다. NP-완전문제인지 판단할 수 있는 쉬운 방법은 없으나 다음과 같은 경우 의심해볼 수 있다.
- 항목이 적을 때는 알고리즘이 빠른데, 항목이 늘어나면 급격히 느려지는 경우
- "X의 모든 조합"이라는 말이 나오는 경우
- 더 작은 하위 문제로 변환할 수 없어서 X의 가능한 모든 버전을 계산해야 하는 경우
- 문제가 수열을 포함하고 풀기가 어려운 경우
- 문제가 집합을 포함하고 풀기가 어려운 경우