23. 근사 알고리즘(Approximation Algorithm)

  이번이 드디어 알고리즘 마지막 시간이다. 마지막 답게 아직 풀리지 않고 있는 알고리즘에 대해 소개하는 시간을 갖겠다. 근사 알고리즘이라는 말에서도 알 수 있듯이 해당 알고리즘들은 아직 풀리지 않고 있기에 정확한 해를 구하지 못해 최대한 근사한 해를 구하는 방법을 알아내는 것이다. 수학 혹은 컴퓨터공학에서 가장 유명한 밀레니엄 문제 중 하나 인 P-NP 문제에 대해 소개하고 대표적인 NP 문제에 대한 코딩을 해보며 마지막 알고리즘 포스팅을 마쳐볼까 한다.

  

  필자가 어릴적에 했던 재밌는 게임 중에서 '한붓그리기' 게임이 있었다. 그 게임은 간선과 정점으로 이루어진 그래프가 주어졌을 때, 각각의 간선을 딱 한번씩만 방문해서 모든 정점을 방문 할 수 있는 경로를 찾는 게임이었다. 이를 이산수학에서 오일러 회로 (Euler Circle)라고 한다. 한붓그리기 문제를 풀기 위해서는 모든 정점을 시작점으로 잡고 주위에 있는 경로들을 탐색해가며 모든 정점을 방문 할 수 있는지 찾아내야 한다. 만약 정점의 개수가 적은 숫자라면 쉽게 풀 수 있겠지만, 만약 정점의 개수가 100개라고 생각해보면, 해당 문제를 쉽게 풀 수 없다. 만약 우리가 풀고자 하는 문제가 다항식 시간으로 떨어지게 되는 문제를 우리는 P(Polynomial) 문제라고 하고, 다항식 시간안에 해결 할 수 없는 한붓그리기 같은 문제를 NP(Non-deterministic Polynomial) 문제라고 한다.

1. P-NP 문제

  P문제와 NP문제의 개념 자체는 그리 어렵지 않다. 우리가 지금까지 풀고 있던 많은 문제중 Yes or No로 떨어지게 되는 문제를 결정문제라고한다. 이런 결정 문제의 해를 구하기 위해 우리는 하나의 알고리즘을 만들게 된다. 예를 들어 하나의 집합에 관해 2개의 문제가 있다고 하자. 

집합 A = {1, 2, -47, 99, 38, -124, 35, -3}

문제 1. 집합 A의 모든 원소의 총 합계는 3이 맞는가?

문제 2. 집합 A의 원소 중 합계 가 0이 되는 부분 집합이 존재 하는가?

  1번 문제는 너무 쉽게 구할 수 있다. 모든 원소의 합계를 계산해 3이라는 숫자와 비교하면 끝나는 문제다. 위에 문제로 보자면 모든 원소를 다 더해서 나온 값이 1이므로 3과 비교해서 값이 맞지 않으므로 위 문제가 No라고 알 수 있다. 이 문제는 다항식 시간안에 충분히 풀 수 있으므로 P 문제에 해당한다.

  2번 문제 같은 경우 집합 A의 모든 부분 집합을 구해서 합계가 0이 되는지 확인을 해야 한다. 모든 부분집합을 대상으로 테스트를 하지 않는 이상 답을 찾을 수 없다. 물론, 누군가가 다항식 시간안에 위 문제를 풀 수 있는 방법을 찾아 낸다면 이 문제도 P 문제가 될 수는 있다. 하지만, 부분집합의 합 문제는 아직까지는 대표적인 NP 문제에 해당한다. 우리가 만약 문제 2번의 답을 알고 있다고 생각하자. 그렇다면 검산 작업은 쉽게 끝난다. 누군가가 옆에서 {1, 2, -3}이라는 답을 알려 줬다고 하면 검산은 매우 쉽게 끝난다. 1,2,-3의 합계를 구하고 이것이 0이 되기 때문에 위 문제의 답이 Yes 라는 것을 알 수 있다.

  많은 수학자와 컴퓨터공학자의 관심은 P 문제 = NP 문제 라는 공식이 성립 하는지이다. 우선, 모든 P문제는 NP 문제에 속한다. P 문제가 다항식으로 해결 할 수 있는 문제이다. P 문제 역시 NP 문제처럼 누군가 힌트를 알려 준다면 쉽게 Yes 라는 사실을 알 수 있다. 따라서 P⊂NP는 성립한다.

  문제는 반대 케이스이다. 과연 우리가 NP 문제를 P 문제라고 할 수 있는가 하는 것이다. 문제 2번은 분명 답이 존재하고 답을 안다면 쉽게 문제를 해결 하겠지만, 그 답을 찾는 과정을 다항식 시간안에 끝내지 못한다. 하지만, 우리가 저 문제를 다항식 시간으로 풀 수 있었다면은 우리가 NP라고 생각했던 문제는 P가 되는 것이다. 따라서, NP⊂P가 성립하며 자연스럽게 P=NP가 된다.

  

  하지만 아직 어느 누구도 P=NP인지 P≠NP인지 증명해내지 못하고 있다. 쉽게 설명하면 우리가 다항식 안에 해결하지 못한다는 것이 실제로는 다항식에 해결 할 수 있다면 혹은 다항식 시간안에 풀어내지 못하는 문제들의 다항식 해가 존재하지 않다는 것을 증명해 낸다면, 이 문제는 해결 된다. 이를 P-NP 문제라고 하고, 이 문제의 해결을 하는데 무려 100만달러의 상금이 걸려있다.

2. NP-완전 문제

  NP 문제는 해를 찾는 방법이 아닌 해를 추측하는 방식이다. 무슨 말인가 하면 위의 NP 문제를 살펴보자. NP 문제를 풀기 위해서 우리는 2가지 단계를 거치게 된다. 첫번째는 해를 추측하기 위해 집합 A의 부분집합 하나를 찾아내야 한다. 여기서 추측을 하는 이유는 해당 문제를 다항식 시간안에 풀어낼 수 없기 때문에 하나의 해를 임의로 정하는 것이다. 하나의 해를 정했다면 문제를 검산하는 작업은 어렵지 않다. 부분 집합을 모두 더하면 된다. 이 과정을 용어로 풀어서 설명하면 처음에 해를 찾아내는 것을 '추측 (Guessing)', 검산하는 작업을 '검증 (Verification)'이라고 한다. NP 문제는 이 두가지 과정을 통해 해를 구하게 된다. 부분집합의 해 뿐만 아니라 오일러 회로 문제에도 똑같이 대입해서 문제를 풀면 된다. 회로 하나를 '추측' 하고 이 경로가 한 붓 그리기가 가능한지 '검증'한다. 

  

  위의 설명처럼 다항식 시간안에 구할 수 없는 문제들을 다른 다항시간안에 풀수 있는 다른 문제로 환원해서 푸는 문제들을 우리는 특별하게 NP-난해(NP-Hard) 문제라고 한다. 다항식 시간안에 도저히 풀 수 없기에 난해라는 이름을 붙였고, 이런 문제들을 위 처럼 추측과 검증 과정을 통해서만 결정 해를 구할 수 있다. 그리고, NP문제 이면서 NP-난해 문제를 우리는 NP-완전 문제(NP-complete) 라고 한다. 즉, P-NP 문제는 'NP-완전 문제가 P문제가 맞느냐 아니냐'를 증명하는 것이다. 

  NP-완전 문제의 가장 큰 특징은 하나의 문제를 다항식 시간 안에 풀 수 있으면 모든 문제를 다항식 시간안에 풀 수 있게 된다. NP문제 같은 경우 NP-완전 문제는 우리가 다항식 시간안에 풀 수 없는 문제를 다항식 시간 안에 풀 수 있도록 변환하는 것이다. 따라서 A 문제를 다항식 문제로 풀기 위해 입력 변환을 하고 새로운 알고리즘을 사용하고 출력 변환 작업을 거쳐 해를 구하게 된다. 부분 집합의 해를 구하는 문제로 설명해보자.

<부분 집합의 해>

부분 집합의 해(NP) -> 입력 변환 : 분할 작업(P) -> 합계 계산 -> 출력 변환 : 정답 여부 판단 -> NP 문제 해결

  아까 설명 했던 추측과 검증 과정을 다르게 설명하면 위와 같을 것이다. 우리는 NP 문제를 다항식 시간안에 다른 문제로 환원해 문제를 해결 한다. 이 구조에서 결국 합계 계산 부분이 다항식 시간 안에 해결 된다면 이 문제는 더이상 NP 문제가 아니게 된다. 결국 하나의 NP 문제에 대해 다항식 알고리즘을 구한다면, 입력 변환 시간이 다항식 시간에 가능하므로 모든 NP 문제가 다항식 시간 안에 풀 수 있게 되는 것이다.

  아직 증명은 되지 못했으나 많은 수학자들이 직관적으로 P≠NP라고 생각하는 이유도 위와 같다. 하나의 NP 알고리즘을 다항식으로 해결하면 모든 NP 문제는 P문제가 되겠지만, 수많은 NP 문제들이 아직까지도 풀리지 않는 다는 것은 결국 NP가 P문제가 아니기 떄문이지 아닐까라고 추측한다. 물론, 일부 학자들이 위와 같은 의견에 반발할 수 도 있는 점은 분명하다. 어쩃든 위의 가정이 맞다는 전제하에 P 문제와 NP 문제의 다이어그램은 아래와 같이 표현된다.

3. 근사 알고리즘 (Approximation Algorithm)

  이제 지금까지 설명한 NP-난해 문제를 어떻게 해결 할 수 있는지 살펴보자. 다항식 시간안에 푸는 방법이 없으므로 앞에서 말했던 다른 문제로의 환원 작업이 필요하다. 이 중 대표적인 2개의 근사 알고리즘에 대해 소개해보도록 하겠다. 

- 분기 한정법 (Branch and Bound)

  분기 한정법은 일정한 범위를 정하고 이 안에 해결이 가능한지 분석을 반복적인 시행착오를 통해 해를 구하는 방법이다. 늘 그렇듯 알고리즘을 말로 설명하는 것은 바보 같은 짓이다. 대표적 Branch and Bound 문제인 순회화는 외판원 문제 (Traveling Salesperson Problem, TSP)를 살펴보자.

  외판원 한명이 1번을 시작점으로 총 다섯 지역을 최소시간으로 방문하려고 한다. 그리고 지점에서의 거리는 다음과 같다.

0 1 6 2 7

1 0 2 1 7

6 2 0 3 2

8 5 2 0 4

7 3 2 1 0

  각 지점에서 다른 지점으로 가는 거리를 나타내는 Matrix이다. 예를 들어 1번 지점에서 5번 지점으로 가려면 총 7의 시간이 소요되고, 2번에서 4번 지점으로 이동하려면 1의 시간이 소요된다. 

  분기 한정법은 해를 구하기 위한 범위를 정하는 작업이다. 위 매트릭스의 각 열은 각 정점에서 다른 지역으로 가는데 걸리는 시간을 의미한다. 즉 각 열에서 자기 자신으로 이동하는 0을 제외하고 최소로 방문 하는 정점들을 하나씩 선택하여 최소 값을 구할 수 있다. 이 값이 분명 우리가 구하려는 해는 아닐 것이다. 하지만, 해당 거리보다는 분명 크거나 같은 값이 나올 것이다.

첫번째 Bound = min (1, 6, 2, 7) + min (1, 2, 1, 7) + min (6, 2, 3, 2) + min (8, 5, 2, 4) + min (7, 3, 2, 1)

  = 1 + 1 + 2 + 2 + 2 = 8

  두번째 분기를 설정하기 위해서 하나의 가정을 해보자. 1번 정점에서 2번 정점으로 가는데 소요되는 시간은 1이다. 이 경로를 고정 시키고 최소값을 구하는 것이다. 1-2간선은 무조건 간다는 가정하에 다른 최소 정점들을 구하는 것이다. 2번 정점을 갔다고 가정했으므로 2번 정점으로 가는 간선을 포함하지 않고 최소값을 구하면 된다.

두번째 Bound = (1,2) 시간 + min (2, 1, 7) + min (6, 3 ,2) + min (8, 2, 4) + min (7, 2, 1)

  = 1 + 1 + 2 + 2 + 2 = 8  

  

  두번째 분기의 경우 1번에서 각 정점을 간다고 예상해야 하므로, 한번의 계산으로 끝나지 않을 것이다. 위의 계산이 2번 정점을 대상으로 한 것이었고, 똑같이 3, 4, 5에 대해 진행을 해야 한다. 따라서 두 번째 Bound를 모두 진행한다면 2~5번 정점에 대한 분기는 8, 16, 9, 13으로 나오게 되고 (1,2) 정점이 선택되고 두번째 Bound 계산을 마친다.

  같은 방법으로 세번째 Bound를 계산한다. (1, 2)가 선택 되었으므로, 1-2-3 / 1-2-4 / 1-2-5 로 간다는 가정 하의 최소 거리들을 구하면 된다.

세번째 Bound (1-2-3) = 1 + (2,3) 시간 + min (6, 3, 2) + min (8, 4) + min (7, 1)

= 1 + 2 + 2 + 4 + 1 = 10

세번째 Bound (1-2-4) = 1 + (2,4) 시간 + min (6, 2) + min (8, 2, 4) + min (7, 2)

= 1 + 1 + 2 + 2 + 2 = 8

세번째 Bound (1-2-5) = 1 + (2,5) 시간 + min (6, 3) + min (8, 2) + min (7, 2, 1)

= 1 + 7 + 3 + 2 + 1 = 14

  이렇게 1-2-4의 경로가 선택되었다. 이와 같은 Bound 계산을 지속하면 1->2->4->3->5->1로 돌아오는 것이 최단 경로라는 점을 알 수 있고, 거리는 총 13이다. 이처럼 각 단계 별로 가장 짧게 가는 정점을 순차적으로 구하는 방법이 바로 분기한정법인 Branch and Bound이다. 

- 이분법(Bisection Method)

  이분 법은 매우 쉽고 간단한 근사 알고리즘이다. 이전에 배웠던 이진 탐색과 비슷한 방법이다. 우리가 다항식 그래프의 해를 구하는 데 이분법을 사용하면 매우 느리지만 근사한 해를 찾을 수 있긴 하다. 아래와 같은 그래프가 있다고 생각하자.

  다항 방정식에서 우리가 구하고자 하는 루트해는 f(x) = 0 이되는 저 빨간 점이 될 것이다. 하지만, 3차 이상의 다차 함수 혹은 지수함수 등 기타 복잡한 함수들은 쉽게 루트해를 구하지 못하는 경우도 있다. 그렇기에 우리가 임의로 a, b를 설정하고 f(a)와 f(b)의 부호가 다르다면 범위를 점차 좁혀나가서 우리가 원하는 해를 구할 수 있다. 근사 알고리즘의 종료를 위해 우리는 허용 오차 혹은 최대 반복 횟수가 필요하다. 둘 중 하나를 설정해 우리가 좁힌 이분 거리의 길이가 허용 오차 이내라면 이분 법을 종료한다. 마찬가지로 횟수를 설정해 해당 횟수에 도달하면 이분법을 종료 시킬 수 도 있을 것이다. 

  매우 직관적이고 간단한 근사 알고리즘이지만 매우 느리다는 것이 단점이다. 만약 우리가 해를 알고 있다면 대입법을 사용해 쉽게 구한다. 1차 함수였다면 대입법으로, 2차 함수였다면 근의 공식으로, 삼각함수라면 우리가 알고있는 상식으로 너무나 쉽게 풀 수 있기 때문이다. 

  이분법의 Pseudo Code는 아래와 같다.

4. 해밀턴 경로 (Hamiltonian Cycle)

  해밀턴 경로 역시 대표적인 NP 문제이다. 앞서 처음에 설명했던 한붓그리기와 비슷한데, 정점과 간선으로 이루어진 그래프 상에서 간선을 딱 한번씩만 이용해 모든 정점을 방문 해야한다. 단, 오일러 회로와는 차이점이 분명 존재하는데 오일러 회로는 모든 간선을 방문해야 하는 대신 정점의 경우 여러번 방문해도 상관없다. 하지만, 해밀턴 회로는 반드시 모든 간선을 지나야 할 필요는 없지만, 모든 정점을 딱 한번씩만 거쳐야한다. 아래 예시를 살펴보자.

  

  오일러 회로 : 모든 간선을 방문해야 하나 간선을 한번만 방문하고 정점을 여러번 거쳐도 가능 하는 경로

  해밀턴 경로 : 모든 정점을 방문해야 하나 정점을 한번만 방문하고 지나치지 않는 간선은 발생 할 수 있음

즉, 오일러는 간선 중심으로 도형을 보는 것이고 해밀턴 경로는 정점을 중심으로 도형을 보는 것이다.

  해밀턴 경로 프로그램은 우리가 도형을 입력하면 해밀턴 경로가 존재하는 경우 해당 경로를 노출 시켜주고 그렇지 않으면 해밀턴 경로가 존재하지 않다는 메세지를 보내주어야 한다.

  우선 Input에 대해 정의해보자. 해밀턴 경로를 찾으려는 그래프의 정점의 개수가 N개라고 생각 했을때, N X N 크기의 매트릭스로 표현 가능하다. 입력하려는 그래프의 모양과 이를 행렬로 표현하면 아래와 같다. 

  { {0, 1, 0, 1, 0},

    {1, 0, 1, 1, 1},

    {0, 1, 0, 0, 1},

    {1, 1, 0, 0, 1},

     {0, 1, 1, 1, 0} }

  즉, 입력 부분은 정점의 개수와 그래프를 행렬로 입력할 수 있어야한다.

  문제의 해결 방법을 보자. 앞서 배운 dfs를 이용한다면 쉽게 풀 수 있다. 예를들어 0번 정점에서 시작해서 경로가 있는지 판단한다. 위의 경우에서는 0번 정점으로부터 시작해 연결된 1,3번 정점으로 이동하고 1,3번 정점에서 또 연결된 경로를 검사한다. 최악의 경우로 가정 했을 때, (N-1)번 방문을 하고, N-2번 방문을 하며, 마지막 정점까지 방문해야 하므로 시간복잡도는 O((N-1)!)가 된다. DFS는 매우 좋은 알고리즘이지만, 해밀턴 경로에 적용하기에는 적합한 알고리즘은 아니다.

  하지만, 우리는 이번 시간에 근사 알고리즘을 통해 해밀턴 경로를 구할 것이다. 모든 간선을 점검하는 것은 좋은 방법이 아니다. 근사 알고리즘으로 문제를 해결하기 위해 근사해를 선정해야한다. 근사해를 선정하기 위해 우리는 해밀턴 경로가 가진 특성을 이용해 몇가지 가정을 해야한다. 우선 우리가 구할려는 해밀턴 경로는 모든 경로를 딱 한번씩만 거쳐야 하므로, 시작점이 어느 지점이든 같은 경로를 나타내게 된다. 또한, 한번씩 정점을 거쳐야 한다는 조건으로 인해 해밀턴 경로의 길이는 무조건 정점의 갯수와 같은 길이가 된다. 따라서 0에서 시작한다고 가정해도 무방하고, 해밀턴 경로의 길이는 무조건 N이다.

  이 가정을 이용해 만약, 가지 못하는 간선을 알고 이를 제거한다면 더욱 쉽게 정점을 구할 수 있다. 이 떄 사용하는 가장 좋은 방법이 Backtracking이다. Backtracking 역시 DFS와 같이 정점 끝까지 반복하는 방법이다. 하지만, 가장 큰 차이점은 앞에서 설명한 일반적인 DFS가 모든 정점에 대한 검색을 진행한다면, Backtracking은 간선이 연결된 정점으로 이동하고, 안될 것 같은 부분은 검색도 안하고, 가능할 것 같은 부분으로 바로 돌아가는 것이다. 아래의 그림을 보면 조금 더 이해가 쉬울 것이다. 

   이제 이 과정을 코드로 살펴보자.

<Solution.java>

import java.util.*;
public class Solution {
    public static int size;
    public static boolean map[][];
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // Input
        Scanner sc = new Scanner(System.in);
        System.out.println("Input the size:");
        size = sc.nextInt();
        
        map = new boolean[size][size];
        int temp;
        System.out.println("Input the graph:");
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                temp = sc.nextInt();
                if(temp==0) map[i][j]=false;
                if(temp==1) map[i][j]=true;
            }
        }
        
        //System.out.println(map.length);
        HamiltonCycle hamiltonCycle = new HamiltonCycle();
        hamiltonCycle.findHamiltonian(map);
        
    }
}

<HamiltonCycle.java>

 

public class HamiltonCycle {
    
    public static int size;
    
    boolean isConnect(boolean map[][], int path[], int j, int pos) 
    { 
        if (!map[path[pos - 1]][j]) 
            return false; 
  
        for (int i = 0; i < pos; i++) 
            if (path[i] == j) 
                return false; 
  
        return true; 
    } 
 
    public boolean findCycle(boolean[][] map, int[] path, int pos){
        
        if(pos == size){
        
            if(map[path[pos-1]][path[0]]) return true;
            else return false;
        }
        
        for(int j=1; j<size; j++){
            if(isConnect(map, path, j, pos)){
                path[pos] = j;
                
                if (findCycle(map, path, pos+1)) return true;
                    
                path[pos] = -1;
            }
            
        }
        
        return false;
            
    }
    
    public void printCycle(int path[]) 
    { 
        System.out.println("Solution Exists: Following" + 
                           " is one Hamiltonian Cycle"); 
        for (int i = 0; i < size; i++) 
            System.out.print(" " + path[i] + " "); 
  
        System.out.println(" " + path[0] + " "); 
    } 
    
    
    public void findHamiltonian(boolean[][] map){
        
        size = map.length;
        int[] path = new int[map.length];
        for (int i=0; i<size; i++) path[i]=-1; // backtracking을 위한 변수
        
        path[0]=0;
        
        if(findCycle(map, path, 1)==false){
            
            System.out.println("\nSolution does not exist"); 
            System.exit(0);
            
        }
        
        printCycle(path);
        System.exit(0); 
        
    }
    
}
 

(참고 코드 : https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/)