[알고리즘] 근사 알고리즘

#근사 알고리즘

 

01 기본 개념

🌵 튜링 기계

NP 완전 문제를 살펴보기 전에, 튜링 기계에 대해서 알아보자. 

( Turing - Welchman bombe 의 레플리카    CCL 에 따라 복사 허용 저자 표시   저자   Photographer:  User:Tom Yates   [1] . Author agreed to license image under the terms of the GFDL after an email exchange with  User:Matt Crypto   ) 

튜링 기계 Turing machine

- 컴퓨터의 이론적 모델, 결국 "주어진 입력과 알고리즘으로 동작하는 컴퓨터"

- 구성 요소 → '테이프, 기호, 헤드, 상태, 규칙'로 주어진 테이프와 규칙에 따라 동작하는 기계 

 

이런 튜링 머신은 1. 결정론적deterministic 튜링 기계 2. 비결정론적non-deterministic 튜링 기계로 나누어진다.

 

결정론적 튜링 기계 vs. 비결정론적 튜링 기계

- 결정론적 튜링 기계는 테이프의 위치를 바꾸거니 쓰인 기호를 바꿀 때 한 가지 상태로만 변경 가능하다.

i.e. 순차 처리 컴퓨터

- 반면, 비결정론적 튜링 기계는 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수도 있다.

i.e. 병렬 처리 컴퓨터

 

🪵 다항 시간polinomial time 알고리즘

- 알고리즘의 수행 시간이 입력 크기 n에 대한 다항식으로 표현될 때, 다항 시간 알고리즘이라고 불린다.

- 정리하자면 다룰 수 있는 시간 내에서 해결이 가능할 때, 다항 시간이라고 한다.

- 반대의 개념으로는 지수시간exponential time이 있는데, 지수 시간은 시간내에 해결이 불가능한 다루기 힘든 경우이다.

 

 

🌴 난이도에 따른 문제 분류

두가지의 난이도

- 쉬운tracatable 문제 

: 결정론적 튜링 기계를 이용한 다항 시간 알고리즘이 존재하는 문제

- 어려운intractable 문제

: 결정론적 튜링 기계를 이용한 다항 시간 알고리즘의 존재 여부를 알 수 없는 문제

 

🦔 형태에 따른 문제 분류

- 판정decision 문제 

: '예' 또는 '아니오' 중 하나의 답으로 요구하는 형태의 문제

- 최적화optimization 문제

: 'nxn'이 n+n보다 작은 자연수 n을 모두 찾으시오

클래스 P와 클래스 NP

- 클래스 P → 결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합

즉, 쉬운 문제의 판정 문제를 원소로 갖는 집합 (Yes/No)

 

- 클래스 NP → 비결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합 

 

클래스 P는 클래스 NP의 집합 관계를 갖지만, P != NP이다.

 

 

 

 

 

 

 

 

 

 

 

🌷 변환이란?

- 변환은 문제 A의 입력과 출력을 문제 B의 입력과 출력으로 바꿀 수 있고, 여기서 문제 B를 해결하는 알고리즘을 적용함으로써 궁극적으로 문제 A를 풀 수 있을 때 변환이라고 한다.

 

02 NP-완전 문제 

위에서 배운 내용을 바탕으로 NP-완전 문제에 대해 배워보자.

🍹 완전complete 문제

- 어떤 부류에 속하는 모든 문제가 그 부류에 속하는 어떤 문제 R로 다항식 시간 변환이 가능하다면 문제 R을 그 부류의 완전문제 라고 한다. 

※ 해당 부류의 모든 문제를 대표하는 문제로, 가장 어려운 문제이기 때문에 완전 문제 R을 다항 시간에 해결할 수 있다면 그 부류의 다른 모든 문제도 다항 시간에 해결 가능하다.

🧉 NP-완전 문제

- 클래스 NP에 속하는 모든 문제가 주어진 어떤 문제 A로 다항식 시간 변환되고, 문제 A가 클래스 NP에 속하는 경우 문제 A를 NP-완전 문제라고 함

🧃 NP-하드 문제

하드hard 문제

- 어떤 부류에 속하는 모든 문제가 어떤 문제 R로 다항식 시간 변환이 가능하면 문제 R을 그 부류의 하드 문제라고 함

※ 완전 문제와 다른 점은, 문제 R이 해당 부류에 속하는 조건이 없을 때 하드 문제라고 한다.

NP-하드 문제

- 클래스 NP에 속하는 모든 문제가 주어진 어떤 문제 A로 다항식 시간에 변환되는 경우, 문제 A를 NP-하드 문제라고 함

NP-완전 문제와 NP-하드 문제의 관계

- 모든 NP-완전 문제는 NP-하드 문제이다.

- 하지만, 모든 NP-하드 문제가 NP-완전 문제는 아니다.

 

우리는 이제까지, NP-완전 문제에 대해서 배웠다. 그래서 종류로는 무엇이 있을까?

NP-완전 문제의 종류

외판원 문제 TSP: Traveling salesmans problem

- 여러 도시와 도시 간의 이동에 필요한 비용이 주어진 경우

비용 R 이하로 모든 도시를 한 번씩만 방문하고 처음 도시로 돌아오는 방법이 존재하는지 판정하는 문제

0/1 배낭 문제

- 특정 용량을 갖는 배낭과 n개의 물체가 주어지고 각 물체마다 무게와 이익이 주어질 때,

배낭에 담긴 물체의 이익의 합이 R 이상이 되도록 배낭에 물차를 담는 방법이 존재하는지 판정하는 문제 (물체 쪼개기x)

CNF 만족성 문제

- 정규곱형Conjuctive Normal Form으로 주어진 논리식의 리터럴들에 참 또는 거짓 값을 적절히 지정하여 전체 논리식의 값을 참으로 만들 수 있는 지를 판정하는 문제

해밀토니언 사이클 문제

- 무방향 그래프 G가 주어졌을 때, G의 모든 정점을 한 번씩만 지나가는 사이클이 존재하는 지 판정하는 문제

궤 채우기 문제 

- 용량이 1인 무한개의 궤와 다양한 크기의 개체가 n개 주어진 경우, R개의 궤로 n개의 개체를 전부 수용할 수 있는지 판정하는 문제

파티션 문제

- n개의 양의 정수가 주어졌을 때, 각 집합에 포함된 수의 합이 동일하도록 n개의 양의 정수를 두 개의 집합으로 나눌 수 있는지 판정하는 문제

클리크 판정 문제

- 그래프 G와 정수 k가 주어졌을 때, G가 크기 k인 클리크를 갖는지 여부를 판정하는 문제

※ k개의 정점으로 완전 그래프(모든 정점 사이에 간선이 존재)가 되는 G의 부분 그래프 

버텍스 커버 문제

- 그래프 G와 정수 k가 주어졌을 때, G가 크기 k인 버텍스 커버를 갖는지 여부를 판정하는 문제

※ 버텍스 커버 → 모든 간선이 최소한 하나 이상의 정점에 부수하는 정점의 부분 집합 

※ 버텍스 커버의 크기 → 버텍스 커버를 구성하는 정점의 개수

NP-완전성의 증명

(1) 알려진 하나의 NP-완전 문제 A가 해당 문제 B로 다항식 시간 변환됨을 보인다. 

(2) 해당 문제를 푸는 비결정론적 튜링 기계가 존재함을 보인다.

 

현실적으로, NP-완전문제를 다항시간에 푸는 알고리즘을 존재하지 않는다. 그러므로 우리는 근사 알고리즘을 구한다.

03 근사 알고리즘

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

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

 "반드시 최적은 아니더라도 요구되는 규칙을 위반하지 않는 해결안"

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

외판원 문제

최소 신장 트리(크루스칼 || 프림) + 깊이 우선 탐색 

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

- 임의의 정점 하나를 루트 노드로 지정해서 최소 신장 트리를 깊이 우선 탐색 순서대로 정점을 나열하고 마지막에 첫 정점을 한 번 더 추가한다.

성능 분석 

- 최소신장트리구하기 →O(|V|2)
- 깊이 우선 탐색 하기 → O(|V|2) O(|V|2)

- 사이클 비용 계산하기 → O(|V|)

특징

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

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

궤 채우기 문제

(1) 최초법first fit

- 사용된 궤 중에서 선택한 물체를 넣을 수 있는 최초의 궤에 넣는다.

(2) 최선법best fit

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

(3) 감소순 최초법first fit decreasing

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

(4) 감소순 최선법best fit decreasing

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

성능 분석

▪ 이중 for 루프: O(n2), 정렬: O(nlogn) → O(n^2)

특징

- 4가지 방법 모두 최적해를 보장하지 못함

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

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

버텍스 커버 문제

근사해 도출 방법

- 그래프에서 임의의 간선을 선택하여 이와 맞닿은 두 정점을 모두 버텍스 커버에 포함시키고,

- 두 정점에 부수된 모든 간선을 그래프에서 제거하는 과정을 반복한다. 

성능분석

O(|E|)

특징

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

 

 

 

 

어떠셨나요? 기말을 앞두고 급하게 공부하려다 보니 머리에 들어오지가 않아요 😅

 

모두 열공! 기말 화이팅!