[방송대 알고리즘]근사 알고리즘

근사 알고리즘

1. 기본 개념

튜링 기계

• 컴퓨터의 이론적 모델
• 구성 요소 → 테이프, 기호, 헤드, 상태, 규칙
• 무한한 길이의 테이프, 유한한 개수의 기호와 상태, 상태와 기호에 따른 헤드의 동작을 정해둔 규칙
• 현재 상태와 읽은 기호에 따라 헤드가 테이프의 기호를 쓰거나 좌우로 이동

결정론적 튜링 기계

• 테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때 한 가지 상태로만 변경 가능
• 순차 처리 컴퓨터와 비슷

비결정론적 튜링 기계

• 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수 있음
• 연산 결과가 상황에 따라 달라질 수 있는 연산을 수행
• 병럴 처리 컴퓨터와 비슷

다항 시간 알고리즘

• 알고리즘 수행 시간이 입력 크기 n에 대한 다항식으로 표현
• O(1), O(logn), O(n^2) 등등..
• O(2^n)같은 경우는 다항 시간 알고리즘이 아닌 지수 시간 알고리즘

난이도에 따른 문제 분류

• 쉬운 문제(tractable)
• 결정론적 튜링 기계를 이용한 다항 시간 알고리즘이 존재하는 문제
• 어려운 문제(intractable)
• 결정론적 튜링 기계를 이용한 다항 시간 알고리즘의 존재 여부를 알 수 없는 문제

형태에 따른 분류

• 판정 문제(decision)
• 예 또는 아니오 중 하나의 답으로 요구하는 형태의 문제
• 최적화 문제(optimization)
• 최솟값 또는 최댓값을 구하는 형태의 문제

클래스 P

• 결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합
• 쉬운 문제의 판정 문제 버전을 원소로 갖는 집합
• 예: 주어진 그래프에서 정점 a에서 e까지의 최단 거리가 10보다 작은가?

클래스 NP

• 비결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합
• 예: 최단 경로 문제의 판정 문제 버전
• 예: 외판원 문제의 판정 문제 버전

클래스 P와 클래스 NP의 관계

• 클래스 P는 클래스 NP에 포함됨
• 클래스 P와 클래스 NP가 같다는것은 증명되지 않음

문제 A가 문제 B로 변환 된다

• 문제 A의 입력과 출력을 문제 B의 입력과 출력으로 바꿀 수 있고, 문제 B를 해결하는 알고리즘을 적용함으로써 문제 A를 풀 수 있다.
• 다항식 시간 변환 → 입력과 출력의 형태를 바꾸는데 다항 시간이 소요

2. NP-완전 문제

완전 문제

• 어떤 부류에 속하는 모든 문제가 그 부류에 속하는 어떤 문제 R로 다항식 시간 변환이 가능하다면 문제 R을 그 부류의 완전 문제라고 함
• R은 해당 부류의 모든 문제를 대표하는 문제
• 완전 문제 R을 다항 시간에 해결할 수 있다면 그 부류의 다른 모든 문제도 결국 다항 시간에 해결 가능

NP-완전 문제

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

• 이 문제를 푸는 알고리즘이 존재하는지, 존재하지 않는지도 증명되지 않음

하드 문제

• 어떤 부류에 속하는 모든 문제가 어떤 문제 R로 다항식 시간 변환이 가능하면 문제 R을 그 부류의 하드 문제라고 함 → 어떤 부류 R이 해당 부류에 속한다는 조건이 없음
• 해당 부류에 속하는 어떤 문제보다 풀기 어렵거나 비슷한 정도로 풀기 힘든 문제

NP-하드 문제

• 클래스 NP에 속하는 하드 문제

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

• 모든 NP완전 문제는 NP하드 문제
• 모든 NP하드 문제가 NP완전문제는 아니다.

NP-완전 문제의 종류

외판원 문제(TSP: traveling salesman problem)

• 여러 도시와 도시 간의 이동이 필요한 비용이 주어진 경우, 비용 R 이하로 모든 도시를 한 번씩만 방문하고 처음 도시로 돌아오는 방법이 존재하는지 판정하는 문제

0/1 배낭 문제

• 물체를 쪼갤 수 없는 배낭 문제

CNF 만족성 문제

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

해밀토니언 사이클 문제

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

궤 채우기 문제

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

파티션 문제

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

클리크 판정 문제

• 그래프 G와 정수 K가 주어졌을 때, G가 크기 k인 클리크를 갖는지 여부를 판정하는 문제
• k개의 정점으로 완전 그래프(모든 정점 사이에 간선이 존재)가 되는 G의 부분 그래프

버텍스 커버 문제

• 그래프 G와 정수 k가 주어졌을 때, G가 크기 k인 버텍스 커버를 갖는지 여부를 판정하는 문제
• 버텍스 커버: 모든 간선이 최소한 하나 이상의 정점에 부수하는 정점의 부분 집합
• 버텍스 커버의 크기: 버텍스 커버를 구성하는 정점의 개수

NP 완전성의 증명

1. 알려진 하나의 NP-완전 문제 A가 해당 문제 B로 다항식 시간 변환됨을 보인다.
2. 해당 문제를 푸는 비결정론적 튜링 기계가 존재함을 보인다.

3. 근사 알고리즘

현실적으로 NP문제의 답을 구하기 어렵기 때문에, 최적해에 가까운 해를 구하는 다항 시간 알고리즘을 근사 알고리즘이라고 부름

근사해(가능해)

• 근사 알고리즘이 생성하는 해
• 반드시 최적은 아니더라도, 요구되는 규칙을 위반하지 않는 해결 안
• 최적해를 구할 수 없거나 빠른 시간에 대략적인 해를 찾는 경우에 이용

외판원 문제의 근사 알고리즘

• 최소 신장 트리 + 깊이 우선 탐색
• 주어진 그래프의 최소 신장 트리를 구한다
• 임의의 정점 하나를 루트 노드로 지정해서 최소 신장 트리를 깊이 우선 탐색 순서대로 정점을 나열하고 마지막에 첫 정점을 한번 더 추가
• O(V^2)
• 근사해는 최적해의 두 배를 넘지 않음

궤 채우기 문제의 근사 알고리즘

• 최초법: 사용된 궤 중에서 최초의 궤에 넣는다
• 최선법: 남는 부분이 가장 작게 되는 궤에 넣는다
• 감소순 최초법: 물체의 크기를 감소순으로 정렬 후 최초법
• 감소순 최선법: 물체의 크기를 감소순으로 정렬 후 최선법

특징

• O(n^2)
• 4가지 방법 모두최적해를 보장하지 못함
• 최초법/최선법의 근사해는 최적해의 두 배를 넘지 않음
• 감소순의 근사해는 최적해의 1.5배를 넘지 않음

버텍스 커버 문제의 근사 알고리즘

• 그래프에서 임의의 간선을 선택하여 이와 맞닿은 두 정점을 버텍스 커버에 포함시키고, 두 정점에 부수된 모든 간선을 그래프에서 제거하는 과정을 반복
• O(E)
• 근사해는 최적해의 두 배를 넘지 않음