[CM301] 16. 근사 (Approximation)
![[CM301] 16. 근사 (Approximation)](/CMajor/assets/img/thumbnails/cm301/16.png)
어렵고도 복잡한
이때까지 우리는 간단한 회로 문제부터 시작하여 TSP 문제까지 이르며 다양한 NP-hard 문제들을 살펴보았습니다. 이것들 말고도 굉장히 많은 문제들이 NP-hard임을 알 수 있습니다. 그 중에는 지뢰찾기, 테트리스, 스도쿠, 심지어는 마리오까지 NP-hard 문제라는 것이 밝혀져 있습니다.
하지만 모든 NP-hard가 다 똑같은 수준의 난이도를 가지는 것은 아닙니다. 공간 복잡도 이론에서는 이를 공간과 시간을 얼마나 소비하느냐에 따라 NP-hard를 더 다양하게 나누게 됩니다.
PSPACE
문제를 푸는 데 메모리(공간)의 양이 다항식 크기($n^k$)만큼만 필요할 때, 이 문제들을 PSPACE라고 합니다. 시간이 어마어마하게 많이 걸리더라도, 공간은 효율적으로 사용하는 경우입니다. 체스나 오목 같은 보드게임에서 ‘최선의 수를 찾는 문제’들이 주로 여기에 속합니다.
EXP, NEXP
다항시간 안에 풀 수 있는 P 문제와 비슷하게, 지수 시간($2^{n^k}$) 안에 해결 가능한 문제는 EXP라고 합니다. 우리가 보통 ‘현실적으로 풀 수 없다’고 간주하는 매우 어려운 문제들이 포함되기 시작하는 지점입니다. P-NP의 관계 처럼, 지수 시간 안에 판별할 수 있는 문제를 NEXP라고 부르기도 합니다.
EXPSPACE
문제를 푸는 데 메모리(공간)의 양이 지수 크기($2^{n^k}$)만큼 필요할 때, 이 문제들을 EXPSPACE라고 합니다. 네 가지 중 가장 거대하고 강력한 범주입니다. 메모리를 지수 스케일로 쓸 수 있다는 것은, 사실상 현존하는 대부분의 알고리즘 문제를 다 포함할 수 있을 만큼 넓다는 뜻이기 때문입니다.
복잡도 이론의 기본 원리에 따라, 이 문제들은 다음과 같은 포함 관계가 성립합니다.
\[P \subseteq NP \subseteq PSPACE \subseteq EXP \subseteq NEXP \subseteq EXPSPACE\]왼쪽에서 오른쪽으로 갈수록 문제는 기하급수적으로 어려워집니다. 특히 $P \neq EXP$임이 증명되었기 때문에, 이 계층 구조 중 어딘가에는 반드시 서로 같지 않은 경계선이 존재합니다. 그리고 그 경계선으로 생각되는 가장 대표적인 부분이 P-NP가 되는 것이고요.
‘근사’하기
어려운 문제가 너무 많습니다! 그냥 어려운 것도 아니고, 감도 안 잡힐 정도로 막막한 문제들이에요. 최적의 정답을 찾는 데 시간이 너무 오래 걸려 불가능한 것 처럼 느껴집니다.
이 어려운 문제들 앞에서, 문제를 풀기보다 조금 ‘근사’해져보는건 어떨까요?
‘근사’하는 방법은 간단합니다. 최적의 답은 아니더라도, 비슷한 답을 내는 다항시간의 알고리즘을 대신 사용하는 것입니다. 이를 근사 알고리즘Approximation Algorithm이라고 하며, 많은 최적화 문제에서 자주 쓰이는 방법입니다. 때로는 100년 걸리는 100점짜리 정답보다 1초 걸리는 95점짜리 정답이 훨씬 좋을 때도 있으니까요!
근사비
대신 사용하는 다항시간의 알고리즘이 얼마나 근사를 잘 해내는지 판단하는 척도로 근사비(Approximation Ratio, $\rho$)를 사용합니다. 근사비는 최적 알고리즘이 계산하는 비용($C’$)에 대한 근사 알고리즘이 계산하는 비용($C$)으로 계산합니다. 결과값은 항상 1보다 크게 나오도록 $C’$와 $C$의 위치를 바꿔 주어야 합니다. 그러면 근사비는 항상 1에 가까울수록 좋다는 뜻이겠죠?
\[\begin{cases} \;\text{최댓값을 구하는 문제} : \; C'/C \\ \;\text{최솟값을 구하는 문제} : \; C/C' \end{cases}\]
그래서 우리는 $C’$의 정확한 값을 구하지 않고, 대신 $C’$가 가질 수 있는 상한Upper Bound 또는 하한Lower Bound을 논리적으로 추론하여 비교합니다.
어떤 비용을 최소화하는 문제를 풀고 있다고 가정해 봅시다. 우리는 최적해 $C’$가 얼마인지는 모르지만, 수학적 성질을 이용해서 문제의 해들이 그 크기를 넘을 수 밖에 없는 하한선 $L$을 찾아낼 수는 있습니다. 그럼 이 하한 $L$에 대해 $C/L \leq \rho$라면, 확실히 $C/C’ \leq \rho$라고 말할 수 있게 됩니다($L < C’$이니까요).
이런 방식을 사용한다면, 우리는 입력 크기 $n$에 대한 근사비 $\rho(n)$를 다음과 같이 표기할 수 있습니다.
\[\text{max}\{C'/C, C/C'\} \leq \rho(n)\]그리고 이를 만족하면, 해당 근사 알고리즘은 $\rho(n)$-approximation 알고리즘이라고 부릅니다.
예시: 정점 커버
정점 커버는 NP-complete 문제였습니다. 이를 다항시간으로 근사해보겠습니다.
1
2
3
4
5
6
7
8
9
10
def approx_vertex_cover(G=(E,V): Graph):
C = set() # 정점 커버
while E: # 남는 선이 없을 때까지
(u, v) = random(E) # 남은 선 중 임의의 선을 선택
C = C | {u, v} # C에 두 점을 추가
for (p, q) in E: # 모든 남은 선에 대해
if adjacent((u, v), (p, q)): # 만약 (u, v)와 연결된 선이라면
E = E - {(p, q)} # 해당 선을 남은 선에서 제거
이 근사 알고리즘은 어느 정도의 근사비를 가지고 있을까요? 우선 approx_vertex_cover()를 통해 선택되었던 선 (u, v)들의 집합을 $A$라고 합시다. 이들은 서로 겹치는 점 없이, 따로 떨어져 있는 선들입니다.
정점 커버는 모든 선에 연결되어 있어야 하므로, $A$의 각 선들에도 연결되기 위해 각 선마다 최소 하나의 점이 정점 커버에 포함되어야 할 것입니다. 그러니 일단 이렇게 최적해의 하한을 정할 수 있습니다.
\[C' \; \geq \; \|A\|\]
그리고 approx_vertex_cover()는 $A$에 있는 모든 점을 정점 커버에 포함시키므로, 다음과 같이 쓸 수 있습니다.
따라서 근사비를 계산하면
\[\rho(n)=C/C'=2\]이므로 이 근사는 2-approximation 알고리즘임을 증명할 수 있습니다.
예시: TSP
TSP 또한 NP-complete 문제였는데, 이것도 다항 시간으로 근사해보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def approx_tsp(G=(E,V): Graph, c, r):
mst = Prim(G, c, r) # MST 생성
return mst.preorder() # MST에 대한 전순서를 해밀턴 회로로 반환
def Prim(G=(E,V): Graph, w, s):
for u in V: # 처음엔 어떠한 점도 방문하지 않음
cost(u) = infinite
prev(u) = None
edge = [] # MST 선들을 모아놓을 집합
cost(s) = 0 # 시작점은 거리 0
H = make_queue(V) # 최솟값 큐 생성
while H is not empty:
u = H.delete_min() # 남은 점 중 가장 가중치가 작은 점 u
for e := (u, v) in E: # u와 연결된 모든 점 v에 대해
if cost(v) > w(u, v): # 기존 최소 가중치보다 더 작은 가중치가 나오면
cost(v) = w(u, v) # v의 최소 가중치 갱신
prev(v) = u # 최소 가중치로 연결된 점은 u가 됨
H.decrase_key(v) # v의 거리 갱신
for v in V: # 모든 점에 대해
edge.append((v, prev(v))) # 연결된 MST 선을 추가
return Graph(edge, V) # 만들어진 MST 반환
코드가 뭔가 길지만, 알고리즘 자체는 딱 두 단계 밖에 없습니다. MST를 만들고, 루트에서부터의 전순서를 반환하는 것이죠.
코드가 길어진 이유는 MST를 만들 때 탐욕적 알고리즘 절에서 다루었던 프림 알고리즘을 사용하였기 때문입니다. 몇 가지 다른 점이 있긴 한데, 우선 원래 무작위 점을 선택해 시작점으로 삼았던 것을 따로 매개변수를 통해 받는 것으로 바꾸었습니다. 그리고 프림 알고리즘이 MST 그래프를 반환하도록 만들어주었습니다.
이 근사 알고리즘의 근사비도 구해봅시다. 그런데 이상적인 경우를 고려하기 위해서는 문제에 한 가지 전제를 추가해야 합니다. 이 그래프가 유클리드 공간 위에 있어, 거리에 따라 가중치가 결정된다는 것입니다.
우선 비교를 위한 각 경우를 나눌텐데, MST를 만들었을 때 선택된 선들을 $T$, 그 MST의 선들을 따라 모든 점을 순회한 후 처음으로 돌아가는 경로를 $W$, 그리고 approx_tsp()로 구한 회로를 $H$라고 하겠습니다.
최적해를 가지는 해밀턴 회로를 $H’$라고 했을 때, $H’$에서 처음과 끝 점을 연결하는 선을 제거하면 모든 점을 잇는 신장 트리가 됨을 알 수 있습니다. 그리고 $T$는 신장 트리 중에서도 가중치 합이 최소가 되는 최소 신장 트리이므로, $H’$의 가중치 합은 항상 $T$의 가중치 합보다 크거나 같습니다.
\[c(T) \leq c(H')\]$W$는 $T$의 모든 선을 두 번씩 지납니다. 따라서 다음과 같이 표기할 수 있습니다.
\[c(W) = 2c(T)\]마지막으로 $H$와 $W$를 비교해보면, 삼각 부등식을 활용하여 $W$의 가중치 합이 $H$의 가중치 합보다 항상 크거나 같다는 것을 쉽게 보일 수 있습니다.
\[c(H) \leq c(W)\]
따라서 근사비를 계산하면
\[c(H) \leq 2c(H') \; \rightarrow \; \rho(n)=c(H)/c(H') \leq 2\]이므로 이 근사는 2-approximation 알고리즘임을 증명할 수 있습니다.
‘정말’어려운 TSP
TSP의 근사 알고리즘이 2-approximation 알고리즘인 것은 그래프가 유클리드 공간 위에 있다는 전제가 있어 가능한 것이었습니다. 그러면 아무런 조건도 없는 완전히 일반적인 TSP 문제라면, 다르게 근사할 수 있는 방법은 없을까요?
우리는 해밀토니안 회로 문제(HAM)가 TSP로 환원되어 풀 수 있다는 것을 알고 있습니다.
\[\text{HAM} \leq_p \text{DEC}(\text{TSP})\]하지만 이것은 어디까지나 정확한 알고리즘에 대해서 성립하는 것이고, 근사 알고리즘을 사용해도 똑같이 풀 수 있는 지는 모릅니다.
\[\text{HAM} \leq_p \text{DEC}(\text{TSP}) \; ?\]만약 TSP를 다항시간으로 근사하여 푸는 알고리즘 A가 있고, A가 TSP를 이용하여 HAM을 풀 수 있다면(=HAM을 TSP로 환원하여 풀 수 있다면), 재미있는 결과가 나옵니다. 우리는 이전에 해밀토니안 문제가 NP-hard이고 NP인 것을 보였죠? 그러면 NP-complete가 되는데, A는 NP-complete인 문제를 다항 시간 안에 풀 수 있는 알고리즘이 되어버립니다. 즉, 여기서 내릴 수 있는 결론은…
아직 단정하기는 이르죠. A가 정말 HAM을 풀 수 있는지 보이지 않았으니까요. A가 존재한다면, 이는 1보다 큰 근사비 $\rho$를 가질 것입니다.
이제 A가 어떻게 TSP를 이용해 HAM을 풀 수 있는지, 이전 절에서 사용한 환원 방법을 떠올려봅시다. HAM을 푸는 그래프를 TSP로 풀 수 있도록 완전 그래프로 바꾸었습니다. 원래 있던 선은 가중치를 0으로, 새로 생긴 선은 가중치를 1로 둔 것이 기억날 것입니다.
\[\text{weight}(u, v) = \begin{cases} 0 & (u, v) \in E \\ 1 & (u, v) \notin E \end{cases}\]이제 어떤 그래프 $G=(E, V)$와 그 그래프로 만들 수 있는 완전 그래프 $G’=(E’, V)$를 생각해봅시다. 지금 상황 또한 비슷합니다. 대신 A는 완벽하게 TSP를 풀지 않는 근사 알고리즘이니, 가중치를 위와 같이 잡아도 가중치 합이 0인 회로를 내놓지 않을 수 있습니다. 그러니 가중치를 조금 다르게 잡아 보겠습니다.
\[\text{weight}(u, v) = \begin{cases} 1 & (u, v) \in E \\ \rho\;\|V\| + 1 & (u, v) \notin E \end{cases}\]이렇게 하면 A가 내놓는 회로의 가중치 합은 경우에 따라 두 가지로 나뉘게 됩니다.
경우 1. 회로의 선들이 모두 $G$안에 있을 때, 가중치 합은 $|V|$가 됩니다.
경우 2. 회로의 선들 중 일부가 $G$에 속하지 않을 때, 가중치 합은 최소 $(\rho\;|V| + 1) + (|V| - 1)$이며, $\rho\;|V|$보다는 확정적으로 클 것입니다.
이 두 가지 경우를 종합하면, ‘A가 내놓는 선들의 가중치 합이 $\rho\;|V|$를 넘는가’를 기준으로 $G$의 해밀턴 회로 생성 여부를 판단할 수 있게 됩니다. 즉, 우리는 A를 이용해서 다항시간 안에 HAM을 해결 할 수 있습니다!
이제 가장 중요한 것은 이 근사 알고리즘이 A가 존재하느냐겠죠. 이것은,
모릅니다.
현재로서는 알 수 없어요. 현재로서는 $\text{P} = \text{NP}$ 인지 $\text{P} \neq \text{NP}$ 인지 증명되지 않았기 때문입니다. 그래서 NP-complete인 HAM을 다항 시간 안에 풀 수 있는 알고리즘이 있는지도, TSP를 다항 시간 안에 풀 수 있는 근사 알고리즘이 있는지도 밝혀지지 않았습니다. 오히려 위의 증명과정은 그 반대의 결과를 말해줍니다.
Theorem. TSP의 근사 불가능성
만약 $\text{P} \neq \text{NP}$라면, 모든 $\rho \geq 1$ 에 대해서 $\rho$-approximation인 다항시간의 TSP 근사 알고리즘은 존재하지 않는다.
현재까지는 $\text{P} \neq \text{NP}$가 지배적인 의견이기 때문에, TSP를 다항 시간에 완벽하게 혹은 일반적인 상황에서 근사하는 알고리즘은 영원히 발견되지 않을 것이라는 쪽에 무게가 실려 있습니다.
어렵고 복잡해도
이렇게 우리의 여정은 ‘아직 모르는’영역에서 끝나게 되었습니다. 우리가 공부하는 알고리즘 이론은, 바로 이 ‘모르는 영역’과 ‘불가능해 보이는 영역’ 사이에서 우리가 갈 수 있는 길을 찾아내는 과정입니다. “만약 이 가정이 맞다면, 우리는 최소한 여기까지는 할 수 있다”라는 논리적인 지도를 그리는 과정이죠.
그러니 우리가 어디까지 갈 수 있을지, 앞으로도 쭈욱 지켜보도록 합시다.
