제13강 근사 알고리즘

7.4 근사 알고리즘

최적화 문제에 대해서 최적해에 가까운 해를 구하는 다항 시간 알고리즘

- 근사해 ( 가능해, feasible solution)

   - 근사 알고리즘이 생성하는 해 -> 반드시 최적은 아니더라도 요구되는 규칙을 위반하지 않는 해결안

- 최적해를 구할 수 없거나 빠른 시간에 대략적인 해를 찾는 경우에 이용

 

7.4.1 외판원 문제

(1) 개념과 원리 

외판원 문제란, 여러 도시가 주어지고 도시 사이를 이동할 떄 필요한 비용이 주어진 경우, 최소한의 비용으로 모든 도시를 한 번씩만 방문하고 처음 도시로 돌아오는 방법을 찾는 문제

 - 주어진 완전 그래프의 모든 정점을 한 번씩만 지나가는 사이클 중 가중치의 합이 가장 작은 사이클을 찾는 문제

 

 

> 최소 신장 트리 + 깊이 우선 탐색

 - 주어진 그래프의 최소 신장 트리를 구한다.

 

 - 임의의 정점 하나를 루트 노드로 지정해서

 

최소 신장 트리를 깊이 우선 탐색 순서대로 정점을 나열하고

 

마지막에 첫 정점을 한 번 더 추가한다.

 

(3) 성능 분석  

최소 신장 트리 구하기   >> O( |V|^2 )

깊이 우선 탐색 하기      >> O ( |V|^2 )

사이클의 비용 계산하기 >> O ( |V| )

 

정점의 개수의 비례하는 성능을 갖는다. O ( |V|^2 )

 

(4) 특징

- 근사 알고리즘으로 찾은 근사해는 최적해의 두배를 넘지 않는다.

  - 최소 신장 트리의 가중치는 최적해보다 작거나 같다.

  - 근사해는 최소 신장 트리의 가중치의 두배를 넘지 않는다.

 

 

 

 

 

 

7.4.2 퀘 채우기 문제

(1) 개념과 원리

 서로 다른 여러 크기의 물체들을 최소 개수의 동일한 크기의 퀘에 집어 넣는 문제

  - 용량이 1인 무한개의 퀘와 n개의 개체 집합 S = { S1 : 0 ≤ Si ≤ 1,  1 ≤ i ≤ n }가 주어진 경우 S를 전부 퀘에 넣는데 필요한 최소한의 궤의 수를 구하는 것

 

1. 최초법 first fit 

: 사용된 궤 중에서 선택한 물체를 넣을 수 있는 

  최초의 궤에 넣는다.

 • 사용된 궤 중에서 넣을 수 있는 궤가 없다면 

   새로운 궤에 현재 물체를 넣는다. 

 

2.  최선법 best fit 

:  현재 물체를 넣었을 때 남는 부분이 가장 작게 되는 궤에 넣는다.

 • 현재 물체를 넣을 수 있는 궤가 없다면 새로운 궤에 넣는다. 

 

3. 감소순 최초법 first fit decreasing

:  물체를 크기의 감소순으로 정렬 → 최초법 적용

 

4. 감소순 최선법 best fit decreasing

: 물체를 크기의 감소순으로 정렬 → 최선법 적용

 

 

(3) 성능 분석 

- 이중 for 루프, 정렬 -> O(n^2)

 

(4) 특징

- 네 가지 방법 모두 최적해를 찾는 것을 보장하지 못함

  - 최초법/ 최선법의 근사해는 최적해의 두 배를 넘지 않음

  - 감소순 최초법/ 감소순 최선법의 근사해는 최적해의 1.5배를 넘지 않음

 

 

7.4.3 버텍스 커버 문제

(1) 개념과 원리

 주어진 그래프의 모든 간선과 맞닿은 최소 크기의 정점의 부분 집합을 찾는 문제

  - G=( V, E ), E={ ( u,v ) | u, v ∈ V }, |V| = n 이 주어진 경우, C ⊂ V 인 C중 모든 ( u, v)에 대해 u ∈ C 혹은 v ∈ C를 만족하며 |C|가 최소인 C를 찾는 것

 

 > 근사해 도출 방법

 1. 그래프에서 임의의 간선을 선택하여 이와 맞닿은

   두 정점을 모두 버텍스 커버에 포함 시키고,

 2. 두 정점에 부수된 모든 간선을 그래프에서 제거하는

   과정을 반복

 

(3) 성능분석

간선의 개수 O( |E| ) 

 

(4) 특징 

-근사해는 최적해의 두 배를 넘지 않는다.