근사 알고리즘(1)[여행자 문제, 정점 커버 문제, 통 채우기 문제]

근사 알고리즘 : 최적해의 값에 가까운 해인 근사해를 찾는 대신에 다항식 시간의 복잡도를 가짐.

근사비율 : 근사해와 최적해의 비율. 1.0에 가까울수록 실용성이 높은 알고리즘임

---

<여행자 문제>

최소 신장 트리의 모든 점을 연결하는 특성을 가짐.

 

여행자 문제는 주어지는 문제의 조건에 따라서 여러 종류가 있다. 여기서 다루는 여행자 문제의 조건은 다음과 같다.

1. 도시 A에서 도시 B로 가는 거리는 도시 B에서 도시 A로 가는 거리 와 같다. (대칭성)

2. 도시 A에서 도시 B로 가는 거리는 도시 A에서 다른 도시 C를 경유 하여 도시 B로 가는 거리보다 짧다. (삼각 부등식 특성)

 

Approx_MST_TSP 슈도 코드

 

입력: n개의 도시, 각 도시 간의 거리

출력: 출발 도시에서 각 도시를 1번씩만 방문하고 출발 도시로 돌아오는 도시 순서

1  입력에 대하여 최소 신장 트리를 찾는다.

2  최소 신장 트리에서 임의의 도시로부터 출발하여 트리의 간선을 따라서 모든 도시를 방문하고

   다시 출발했던 도시로 돌아오는 도시 방문 순서를 찾는다.

3  return 이전 단계에서 찾은 도시 순서에서 중복되어 나타나는 도시를 제거한 도시순서

   (단, 도시 순서의 가장 마지막의 출발 도시는 제거하지 않는다.)

 

시간복잡도 : 크러스컬(mlogm), 프림(n^2) 알고리즘의 시간복잡도와 같다.

근사 비율 : 2M/M=2 보다 크지 않다. 즉, 근사해의 값이 최적해의 값의 2배를 넘지 않는다.

---

<정점 커버 문제>

방법1. 차수가 가장 높은 점을 우선 선택한다.

방법2. 극대 매칭을 이용하여 근사해를 찾는다. 

극대 매칭 : 이미 선택된 간선에 기반을 두고, 새로운 간선 추가가 불가능한 매칭.

 

Approx_Matching_VC

입력: 그래프 G=(V,E)

출력: 정점 커버

1  입력 그래프에서 극대 매칭 M을 찾는다.

2  return 매칭 M의 간선의 양 끝점들의 집합

 

시간 복잡도 : O(mn)

근사 비율 : (극대 매칭의 간선의 양 끝점들의 수)/(극대 매칭의 간선 수) = 2

=> 한 개의 간선당 두개의 점이 있으니까.

 

---

<통 채우기 문제>

 

최초 적합, 다음 적합, 최선 적합, 최악 접합과 같은 그리디 알고리즘으로 근사해를 찾는다.

 

최초 적합(First Fit) : 가장 먼저 나온 통부터, 여유가 있는 대로 담는다.

다음 적합(Next Fit): 바로 직전 통의 여유가 되면 담고, 안되면 다음 통에 담는다.

최선 적합(Best Fit):  넣을 수 있는 통들 중에서, 안의 내용물이 높이가 최고인 통부터 담는다. 

(여기서 최선의 의미는 새 물건이 들어가면 남는 부분이 가장 적어서 최선인것.) 

최악 적합(Worst Fit): 넣을 수 있는 통들 중에서, 안의 내용물이 높이가 최하인 통부터 담는다.  

(여기서 최악의 의미는 새 물건이 들어가면 남는 부분이 가장 많아서 최악인것.) 

 

-Approx_BinPacking 슈도코드-

 

입력: n개의 물건의 각각의 크기

출력: 모든 물건을 넣는 데 사용된 통의 수

1  B = 0 // 사용된 통의 수

2  for i = 1 to n {

3      if(물건 i를 넣을 여유가 있는 기존의 통이 있으면)

4           그리디 방법에 따라 정해진 통에 물건 i를 넣는다.

5      else

6           새 통에 물건 i를 넣는다.

7           B = B + 1 // 통의 수를 1 증가시킨다.

    }

8  return B

 

근사비율 : 4가지 모두 2

다음 적합을 제외한 나머지 적합 : 수행시간 O(n^2)

다음 적합 : 수행시간 O(n)