8.1. 근사 알고리즘
다항식 시간에 해결할 수 없는 문제를 다항식 시간안에 해결하기 위해서 최적해가 아닌 근사해를 찾는것
즉 근사 알고리즘이란, 최적해에 아주 근사한 해를 찾아주는 것
8.1.1 NP 완전 문제 해결
NP 완전 문제들을 어떻게든 해결하려면 다음 3가지중에 어느것 1가지를 포기해야한다.
1. 다항식 시간안에 해를 찾는 것
2. 모든 입력에 대해 해를 찾는 것
3. 최적해를 찾는 것
8.1.2 근사 알고리즘의 특징
근사 비율: 근사해의 값과 최적해의 값의 비율로 1.0에 가까울 수록 정확도가 높은 알고리즘 (1보다 큰 수가 나오는것이 일반적)
근사해를 구하기 위해선 최적해가 필요하지만 최적해는 구할 수 없음
따라서 간접적인 최적해를 최적해로 두고 근사비율을 구함
따라서 간접적인 최적해를 통해 얻은 근사비율은 실재 근사비율보다 크거나 같다.
8.1.3 여행자 알고리즘(TSP)
여행자가 임의의 한 도시에서 출발해서 모든 도시를 1번씩만 방문하고 처음도시로 돌아오는 여행 경로의 가중치를 최소화 하는것
- A에서 B로 가는것과 B에서 A로 가는 거리는 같다 (대칭성)
- [A -> B] 는 [A -> C -> B] 보다 짧다 (삼각 부등식 특성)
8.1.3.1 여행자 문제 해결
다항식 시간을 가지면서 유사한 특성을 가지는 알고리즘 사용
최소신장트리(MST) 문제를 활용
MST: 모든 점을 사이클 없이 연결하는 트리중에서 트리 선분의 가중치의 합이 가장 작은 트리를 찾는 알고리즘
- 모든 점을 연결
- 최소의 가중치를 가짐
시작도시를 제외한 모든 도시를 트리의 선분을 따라 1번씩 방문하도록 해 경로를 찾는 방안
1. MST를 가장 먼저 찾는다.
2. MST를 따라 모든 점을 순회한다.
3. 변을 2번 지나는 문제점이 있다.
4. 방문한 지점을 순서대로 나열한다.(한번 지난 점을 다시 지나올 수 없다.)
5. 이미 지나온 점을 삭제한다.
(단 마지막 1번 점은 돌아오는 점이기 때문에 삭제하지 않는다)
8.1.3.2 여행자 문제 최적해
MST 선분의 가중치의 합 = M
최적해 = W(TSP)
M < W(TSP) < 2M
시간복잡도 O(n)
근사비율 2M/M = 2보다 작다 = 약 2
8.1.4 정점 커버 문제
주어진 그래프 G=(V,E)에서 양 끝점중에 적어도 하나의 끝점을 포함하는 점들의 집합들 중에서 최소 크지의 잡합을 찾는 문제
즉, 그래프의 모든 선분을 커버하는 것이다.
(집합 커버 문제와 같은 형태를 가진다)
{1,2,3} {1,2} {1,3} {2,3} {1}이 각각 G의 정점 커버다.
8.1.4.1 정점 커버 문제 해결
다항식 시간을 가지면서 유사한 특성을 가지는 알고리즘 사용
집합 커버 문제를 활용
점을 선택
1. 가장 많은 간선을 포함하고 있는 점을 선택한다
2. 선택한 점이 가지고 있는 간선을 지운다
3. 모든 간선이 사라질 때까지 반복한다
간선을 선택(극대 매칭)
극대 매칭을 찾는다. { 1. 임의의 간선을 선택한다 2. 선택한 간선과 연결되어 있는 간선을 지운다 (선택된 선분의 양 끝점이 지워지는 선분을 커버할 수 있음) 3. 모든 간선이 사라질 때까지 반복한다 } 극대매칭의 양끝 점을 반환한다.
정점의 수 n
간선의 수 m
시간복잡도 O(nm)
근사비율 = 2
(극대매칭의 각선분의 양 끝점의 수)/(극대매칭의 선분 수) = 2
8.1.5 통 채우기 문제
물건의 갯수 n, 통의 용량 C가 주어질 때
모든 물건을 가장 적은 수의 통에 채우는 문제
단, 물건의 크기는 C보다 작다
8.1.6 통 작업 스케줄링 문제
n개의 작업, 각 작업의 수행시간 t, m개의 기계가 주어질 때
작업이 가장 빠르게 종료 되도록 작업을 기계에 배정하는 문제
