알고리즘의 설계 기법
알고리즘 : 박정호, 상조사, 1995. Page 227-253
훌륭한 알고리즘 중에는 문제를 해결하는 방법과 고속화의 테크닉에 있어서 공통점을 가진 알고리즘이 많이 있다. 예를들면 퀵 정렬과 합병 정렬은 정렬 대상이 되는 데이터가 들어 있는 배열을 두 개로 나눠서 두 배열을 각각 정렬한 후, 그들 두 배열을 연결한다는 점에서 공통점을 갖고 있다. 이러한 기본적인 테크닉을 알고리즘의 설계 기법이라고 부른다. 프로그래머는 해결해야 할 새로운 문제에 접했을 때 기존의 알고리즘 설계 기법을 응용할 수 있는지 어떤지를 생각하는 것은 새로운 알고리즘 개발에 필요한 시간과 경비를 줄일 수 있다는 점에서 매우 중요하다. 이 관점에서 여기서는 몇 가지 알고리즘 설계 기법을 소개하기로 한다.
효율이 좋고 알고리즘을 설계하는 기법으로서 가장 널리 사용되고 있는 기법중에 분할 통치법 (divide-and-conquer) 이라는 것이 있는데, 분할 통치법에서는 해결하려고 하는 문제 (크기를 n 이라고 한다) 를 크기가 보다 작은 여러 개의 부분 문제로 분할한다. 단, 이 때 크기가 작은 부분 문제에 대한 답으로부터 원래의 문제에 대한 해답을 쉽게 얻을 수 있게 분할할 필요가 있다. 이 기법에 대해서는 합병 정렬과 2 진 탐색목 등 몇 가지 응용 예를 지금까지 살펴보았다.
우선 문제를 분할하면 어느 정도 효과가 있는지를 예를 통해 살펴보기로 하자.
탁구 대회를 열어서 가장 탁구를 잘 하는 사람과 가장 못하는 사람을 정하려고 한다. 실력이 좋은 사람이 항상 이긴다고 했을 때 몇 번 시합을 하면 되는가를 계산하는 것이 문제이다.
여기서 탁구 대회 참가 인원을 n 명이라고 하자. 이 문제를 해결하기 위해서 스포츠 경기시에 일반적으로 많이 이용하는 「토너먼트법」을 이용하는데, 첫 번째 토너먼트에서는 가장 강한 사람을 결정하고, 그 다음에는 나머지 n - 1명 중에서 마찬가지로 토너먼트법을 이용해서 가장 약한 사람을 정하는 방법을 이용하기로 하자 (그림 1). 그림 1 에서 굵은 선은 시합에서 이긴 사람을 나타내고, × 표시가 있는 것은 진 사람을 나타낸다.
그림 1 탁구 대회
그림 1 과 같은 방법을 이용하는 경우에는 한번 시합을 할 때마다 한 사람씩 대상에서 제외되므로, n 명 중에서 가장 강한 사람을 정하기 위해서는 n - 1 번 시합을 하게 된다. 따라서 이 방법에서 필요한 시합수를 T1 (n) 이라고 하면,
이 된다.
그러나,
조금만 곰곰히 생각해 보면 그림 1 과 같은 방법을 이용하는 경우에는 불필요한
시합을 많이 한다는 것을 금방 알 수 있다. 첫 번째 토너먼트에서 이긴 사람 (약 n
/ 2 명) 은
자기가 이긴 상대보다는 강하다는 것은 알고 있으므로 다음 번에 실시하는 토너먼트에는
출전할 필요가 없다. 두 번째 토너먼트전은 첫 번째 토너먼트에서 한번도 이기지
못하고 진 사람만을 모아서 실시하면 되므로, 두 번째 토너먼트에 출전하는 사람수를
k 라고 하면 두 번째 토너먼트전을 운영하기 위해서는 k
- 1 번
시합을 하면 된다.
이
방법으로 경기를 할 때의 시합수를 평가히가 위해서는 k 를 구해야
하는데, 이를 위해서는 첫 번째 토너먼트전을 구체적으로 어떻게 행하는지가 문제가
된다. 이 때 전년도 우승자에게 다른 사람이 차례로 한 사람씩 도전하는 방법을 택한다고
하고, 전년도 우승자가 모두에게 이기면 k 의 값은 n
- 1 이
된다. 따라서, 이 방법을 이용하더라도 그림 1 의 방법과 같이 2n -
3 번
시합을 해야 한다 (그림 2).
그림 2 비능률적인 경기 운영
그러나 n 명을 거의 반씩 나눠서 첫 번째 토너먼트를 하게 하면 k 의 값은 n / 2 이 된다 (그림 3).
그림 3 능률이 좋은 경기 운영
이 때 계산을 간단하게 하기 위해 n을 짝수라 하고, 이 경우의 시합수를 T2(n) 으로 하면,
이 되어, 그림 1 의 방법보다도 n / 2 - 1 번이나 시합수가 적어진다.
그러면, 이번에는 또 다른 방법을 생각해 보기로 하자.
우선 전체를 반으로 나눠서 각 팀에서 따로따로 최강자와 최약자를 결정한 후, 양 팀의 최장자끼리 시합을 하게 해서 전체의 최강자를 정하고, 최약자끼리 시합을 하게 해서 최약자를 정하면 된다 (그림 4).
그림 4 분할에 의한 최강ㆍ최약자 결정
이 방법을 이용한 경우의 시합수를 T3(n) 으로 하면,
가 된다. 또, 분명히
이다. 이 두 식을 이용하면 각 n 에 대해 다음과 같이 되는데, 계산을 간단하게 하기 위해 n = 2p 라고 한다.
이것을 n 에 대한 일반식으로 나타내면,
이 된다.
여기서 설명한 마지막 방법 (그림 4 의 방법) 에서는 우선 전체를 반으로 나눠서 (분할) 각각에 대해 원래와 같은 문제를 해결하고 마지막에 간단한 처리를 해서 전체에 대한 해답을 구한다 (통합). 이와 같이 전체를 분할해서 각각을 따로따로 처리하고 마지막에 통합하는 방법을 「분할 통치법」이라고 한다 (그림 5).
그림 5 분할 통치법의 원리
그림 6 하노이 탑 문제의 초기 상태
분할 통치법의 또 하나의 예로서 하노이의 탑이라는 게임을 생각하기로 하자.
그림
6 과 같이 세 개의 막대 A, B, C
가
있는데, 처음에는 A 라는 막대에 여러 개의 원판이 크기순으로
즉, 어떠한 원판을 보더라도 위에는 그보다 적은 원판이 있고 아래에는 그보다 큰
원판이 놓여져 있다. 이 게임의 목적은 원판을 막대에서 막대로 한번에 하나씩 이동해서
모든 원판을 막대 B 로 옮기는 것이다. 단, 어떠한 경우에도
적은 원판 위에는 큰 원판을 둘 수 없다.
이
게임은 다음과 같은 단순한 알고리즘으로 해결할 수 있다는 것을 알 수 있다. 막대가
삼각형의 형태로 배치되어 있다고 하고 홀수 번째에는 가장 작은 원판을 시계 방향으로
하나만 이동하고, 짝수 번째에는 제일 작은 원판을 제외한 나머지 원판 중에서 이동할
수 있는 것만을 하나 이동한다.
이
알고리즘은 간단하고 정당하지만 왜 정당한지를 금방 알기는 어렵지만 다음과 같은
분할 통치법을 이용하면 정당성도 금방 이해할 수 있을 것이다.
원판
n 장을 A 에서 B 로
이동하는 문제는 크기가 n - 1 인 두 개의 부분 문제로 구성된
것이라고 생각할 수 있다. 우선 n - 1장의 원판을 막대 A 에서
막대 C 로 옮기면 막대 A 에 있던 n
번째
작은 원판 (가장 큰 원판) 을 옮길 수 있는 상태가 되므로 그 원판을 A
에서
B 로 옮긴다.
그리고
나서, n - 1 장의 원판을 막대 C에서 B로
이동한다. n-1장의 원판을 옮기기 위해서는 이 방법을 재귀적으로
사용하면 되는데, 여기서 이동하는 n - 1 장의 원판은 다른 어느
원판보다도 작으므로 이동할 때에 막대 A, B,
C 의 제일 윗부분에는 어떠한 원판이 있는지를 생각할 필요가
없다. 실제로 여러 개의 원판이 어떻게 이동하는지는 알기 어렵고, 재귀 호출이 반복되므로
이것을 하나하나 체크하기는 힘들지만, 이 알고리즘의 아이디어는 이해하기 쉽고
정당하다는 것을 증명하는 것도 비교적 쉽다. 일반적으로 이와 같은 분할 통치법을
이용한 알고리즘은 그렇지 않은 알고리즘보다 효율이 좋다.
분할
통치법을 이용해서 알고리즘을 설계할 때에는 문제를 분할하는 방법 및 각 부분 문제에
대한 답을 통합시키는 방법도 고려해야 한다. 특히 부분 문제의 답에서 전체의 문제에
대한 답이 비교적 간단하게 얻어지지 않으면 이 기법은 사용할 수 없는 것이라고
생각해야 한다. 문제의 분할법도 알고리즘의 성능에 영향을 미치기 때문에 중요한다,
대부분의 경우 가능한 균등한 크기로 분할하는 것이 바람직하다.
부분 문제를 해결하기 위해서는 같은 프로시저를 재귀적으로 호출하는 것이 간단하고, 이 재귀 호출은 데이터수가 1 이 될 때와 같이 문제의 답이 분명하게 되는 시점에서 종료하게 된다.
앞에서 설명한 분할 통치법의 예에서는 모두 원래의 문제를 크기가 같은 부분 문제로 분할했는데, 좋은 알고리즘을 설계하기 위한 기본적인 지침 중에 부분문제의 크기가 균등해야 한다는 것이 있다. 이것을 설명하기 위해서 정렬의 예를 사용해서 문제를 균형이 맞지 않는 크기를 가진 부분 문제로 분할한 결과와 같은 크기로 분할한 결과를 비교해 보자. 이 예에서 균형화가 유효하다는 것은 분할 통치법에만 한정된 것이라고 생각해서는 안된다.
n 개의 정수로 구성된 데이터를 크기가 적은 순으로 정렬하는 문제를 생각해 보자. 이 문제를 해결하기 위한 가장 단순한 정렬법은 데이터열을 앞에서부터 차례대로 조사해서 가장 작은 요소를 찾아낸 뒤, 제일 왼쪽에 있는 데이터와 교환하고, 그 다음에는 제일 왼쪽에 있는 데이터를 제외한 데이터열을 앞에서부터 차례대로 조사하여 가장 작은 요소를 찾아낸 뒤, 왼쪽에서 두 번째에 있는 데이터와 교환하는 것을 반복하는 것이다. 이 과정을 나머지 데이터에 대해서도 반복 적용함으로써 n 개의 데이터에 대한 정렬을 할 수 있다.
이 알고리즘에 의해 정렬되는 요소 사이에서 행해지는 비교 횟수를 평가해 보자. 제일 적은 데이터를 정하기 위해서는 n - 1 번 비교를 해야 하고, 두 번째 작은 데이터를 정하기 위해서는 n - 2 번, 그 다음 데이터를 정하기 위해서는 n - 3 번을 비교해야 한다. 전체 비교 횟수는 이들을 합하면 되므로,
이
되어 O(
) 이 된다.
이 정렬 알고리즘은 크기가 다른 부분 문제로 분할하는 분할 통치법을 재귀적으로 적용한 것이라고 볼 수가 있지만 크기 n에 대해서는 효율이 좋지 않으므로 오더상으로 효율이 좋은 정렬 알고리즘을 설계하기 위해서는 부분 문제의 크기를 균등화해야 한다. 크기가 n 인 문제를 크기 1 과 크기 n - 1 인 두 부분 문제로 분할하지 않고, 문제를 크기가 거의 반인 두 개의 문제로 분할해야 하는데, 이것은 앞에서 이미 설명한 합병 정렬이라는 정렬 알고리즘에서 이용되고 있다.
합병 정렬에 대해서는 이미 설명했으므로 알고리즘에 대한 설명은 생략하지만 이미 설명한 바와 같이 이 알고리즘의 복잡도는 O(n log n) 이다.
이와 같이 부분 문제의 크기를 균등하게 함으로써 훨씬 효율이 좋은 알고리즘을 만들 수 있게 된다.
재귀적인
기법은 문제를 간단히 부분 문제로 분할할 수 있고, 부분 문제의 크기의 합을 적게
유지할 수 있는 경우에 유효하다. 그러나, 크기가 n인 문제를 단순히 분할해서 각
부분 문제의 크기가 균형이 맞지 않는 문제로 분할되었을 때에는 재귀적 알고리즘의
복잡도는 아마 지수 함수적으로 증가할 것이다. 이런 경우에는 「동적 계획법」이라는
기법을 이용하면 효율좋은 알고리즘을 설계할 수 있다.
문제를
크기가 적은 부분 문제로 분할한 뒤 부분 문제에 대한 답을 구하기 위해 같은 부분
문제를 몇 번이고 반복해서 해결할 필요가 있는 경우가 있다. 그 때에는 한번 해결한
부분 문제의 해답을 「표」에 기억해 두었다가 필요할 때에 그 표를 참조하게 하면
새로 계산하는데 걸리는 시간을 절약할 수 있게 되어 효율이 좋은 알고리즘을 얻을
수가 있다.
이와
같이 경우에 따라서는 언젠가는 해결하게 될 모든 부분 문제의 해답을 표로 해두는
것이 프로그램을 작성하기 쉬운 경우도 있다. 어떤 부분 문제가 실제로 전체의 문제
해결 과정에서 필요하게 되는지 어떤지는 생각하지 않고 일단 표를 작성하는데, 이와
같이 주어진 문제를 해결하기 위해 부분 문제에 대한 답을 표에 기입하는 기법을
동적 계획법 (dynamic programming) 이라고 한다. 동적계획법이라는 이름은 제어 이론에서
나온 것이다.
본질적으로는 동적 계획법은 모든 부분 문제에 대한 답을 계산하는데, 계산은 크기가 작은 부분 문제로부터 보다 큰 부분 문제로 답을 표에 기록하면서 나아간다. 동적 계획법의 장점은 한번 어떤 부분 문제가 해결되면 답을 기억해 둠으로써 결코 두 번 다시 계산되지 않는다는 것이다. 이 기법은 간단히 예를 보면 쉽게 이해할 수 있을 것이다.
먼저
다음과 같은 n 개의 행렬을 곱하는 문제를 생각하기로 한다. 단, 각 행렬 
의 크기는 
행, 
열로 한다.
행렬을 곱하는데 어떤 알고리즘을 이용하더라도 행렬이 곱해지는 순서가 M 을 계산하는데 필요한 연산의 총수에 영향을 미친다.
연산 순서와 연산하는 횟수와의 관계를 보기 위해 다음과 같은 실제적인 행렬 곱셈을 예로 들어보기로 하자.
괄호속에
있는 수는 각 행렬 
의 치수를 나타낸다. 일반적인 방법을 이용하면 p × q차 행렬과 q ×
r 차 행렬의
곱셈은 p × q × r 번의 연산을 필요로 하므로, M 을 
의 순으로 계산하면 125000 번의 연산이 필요하지만 
순으로 계산하면 2200 번의 연산이면 된다. 이들 연산수를 살펴보기 위해 다음과
같은 동적 계획법을 이용하면 된다.
행렬의 곱셈에 필요한 연산수를 최소화하기 위해서는 n 개의 행렬을 곱하는 순서를 모두 체크하면 되지만 이것은 막대한 시간과 노력을 필요로 한다. 그러나, 동적 계획법을 이용하면 복잡도가 O(n3) 의알고리즘을 얻을 수가 있는데, 행렬의 곱셈을 하는데 연산수가 가장 적은 방법을 찾기 위해서는 동적 계획법을 어떻게 이용하는지를 설명하기로 한다.
mi, j가 mi × Mi+1 × … × Mj 를 계산하는데 걸리는 시간 중에서 가장 적은 시간이라 하고, 이것을 식으로 나타내면 다음과 같다.
위의
식에서 첫 번째 항인 mi, k 는 M' = Mi ×
Mi+1 × … × Mk 를
계산하는데 걸리는 시간 중에서 가장 적은 시간을 나타내고, 두 번째 항인 mk+1,
j 는 M″ = Mk+1 × Mk+2
× … × Mj 를 계산하는데
걸리는 시간 중에서 가장 적은 시간을 나타낸다. 단, M′ 는 ri-1 ×
rk 차
행렬, M″ 는 rk × rj 차 행렬이다. mi, j
는 모든
k(i ≤ k ≤
j - 1) 에
대해 이들 세 항을 합한 값이 가장 적은 값이라는 것을 나타낸다.
이
동적 계획법에 의한 방법에서는 첨자의 값의 차가 적은 순으로 mi, j
를
계산해 간다. 즉, 모든 i 에 대해 mi, i 를 계산하는
것에서부터 시작해서 mi, i+1 과 mi, i+2
순으로 계산한다.
M = M1
× M2 × M3
× M4 를
계산하는데 이 알고리즘을 적용하기로 한다. 단, r0,
r1, r2, r3,
r4는 10, 20, 50, 1, 100 이고 mi,
j 의 값을 계산한 결과는 다음과 같다. 따라서, 곱셈을 하는데 필요한 최소의
연산수는 2200 이 된다.
m1, 1 = 0 |
m2, 2 = 0 |
m3, 3 = 0 |
m4, 4 = 0 |
m1, 2 = 10000 |
m2, 3 = 1000 |
m3, 4 = 5000 |
|
m1, 3 = 1200 |
m2, 4 = 3000 |
|
|
m1, 4 = 2200 |
|
|
|
동적 계획법에 대한 또하나의 예로서 다각형을 삼각형으로 분할하는 최소삼각형 분할 문제를 생각하기로 한다.
삼각형 분할 문제란 다각형의 정점과 각 정점간에 거리가 주어져 있을 때, 서로 인접하지 않는 두 정점 사이에 새로 선(arc)을 그어서 다각형 전체를 삼각형으로 분할하는 것이다. 삼각형 분할 문제 중에서 삼각형으로 분할하기 위해 정점과 정점 사이에 그어진 선의 길이의 합을 최소화하는 문제를 최소삼각형으로 분할하기 위해 정점과 정점 사이에 그어진 선의 길이의 합을 최소화하는 문제를 최소삼각형 분할 문제라고 한다.
그림 7 7 각형과 삼각형 분할의 예
그림 8 삼각형 분할의 예
그림
7 에 7 각형과 각 정점에 대한 (x, y)
좌표를
나타내는데 거리 함수는 일반적인 유클리드 거리로 한다. 그림 7 에서 삼각형 분할의
한 예를 점선으로 나타냈지만 예를들면 그림 8과 같은 삼각형 분할이 있으므로
이것은 최소삼각형 분할이 아니다. 그림 7과 같은 분할의 코스트는 변 (1, 3), (1,
4), (1, 6), (4, 6) 의 길이의 합계
즉, 
이고, 그림 8 과 같은 분할 코스트는 변 (1, 3), (1, 4), (1, 5), (1, 6) 의 길이의
합계 즉, 
=45.16이다.
이
삼각형 분할 문제에 동적 계획법을 적용하기 전에 삼각형 분할이 가지는 두 가지
성질을 정리해 두고, 그들 성질을 알고리즘 설계에 이용하기로 한다. 다각형에는
시계 방향으로 n 개의 정점 v1,
v2, …, vn 이 있다고 한다.
[성질 1] 세 정점 이상으로 구성된 다각형을 삼각형 분할했을 때 다각형의 변과 접해 있는 두 정점은 반드시 하나 이상의 선과 접해 있다. 만일 vi 과 vi-1 이 모두 어떠한 선과도 접하지 않는다고 하면, 변 (vi, vi-1) 이 에워싸고 있는 영역에는 변(vi-1, vi) 과 (vi+1, vi+2) 외에 하나 이상의 변이 포함된다. 이렇게 되면 이 영역은 삼각형이 되지 않는다.
[성질 2] 어떤 삼각형 분할에서 (vi, vj) 를 선이라고 하면, (vi, vk) 와 (vk, vj) 가 모두 다각형의 변 혹은 선이 되는 vk 가 여러 개 존재한다. 그렇지 않으면 (vi, vj) 가 삼각형이 아닌 영역을 에워싸고 있는 것이 된다.
다음은 앞의 두 개의 성질을 이용하여 최소삼각형 분할 문제를 해결하는 알고리즘을 설명하기로 한다.
최소삼각형 분할을 하기 위해 우선 인접하는 두 정점 v0 과 v1을 선택한다. 위에 기술한 두 성질은 임의의 삼각형 분할에서 성립하므로 최소의 삼각형 분할에서도 성립한다. 따라서 (v1, vk) 와 (vk, v0) 가 모두 삼각형 분할에서의 선 혹은 변이되는 정점 vk 가 존재한다. 이 때, 여러 개의 k 가 존재하면 어느 경우에 어느 정도 좋은 삼각형 분할을 할 수 있는지를 생각해야 하는데 n 개의 정점을 가진 다각형이라면 모두 (n - 2) 개의 선택이 가능하다.
어느 k 를 택하더라도 그로 인해 생기는 부분 문제는 많아야 두 개인데, 그들은 선택한 선의 양쪽 끝에 있는 두 정점을 잇는 원래의 다각형의 변에 의해 구성되는 두 개의 다각형에 대응한다. 예를들면 정점 v3 를 선택하면 그림 9에 나타내는 두 개의 부분 문제가 생긴다.
그림 9 v3 을 택했을 때의 부분 문제
다음은 그림 9(a), (b) 의 다각형에 대한 최소삼각형 분할을 해야 하는데, 그를 위해서는 또 인접하는 두 정점에서 나오는 선을 모두 생각해야 한다고 여겨진다. 예를들면 그림 9(b) 를 해결하기 위해서 선 (v0, v3) 과 같은 부분 문제의 선과 그외의 정점으로 삼각형을 만들어야 한다. 가령 v4 를 선택했다고 하면 삼각형 (v0, v3, v4) 와 부분 문제 (v0, v4, v5, v6) 이 생기고, 이 부분 문제 중에서 원래의 다각형의 선은 하나 뿐이다. 한편, v4 가 아니라 v5 를 선택하면 부분 문제 (v3, v4, v5) 와 (v0, v5, v6) 이 생기는데 각 부분 문제에 대한 선은 (v3, v5) 와 (v0, v5) 뿐이다.
일반적으로 정점 vi 에서 시작해서 시계 방향으로 s 개의 정점 vi, vi+1, …, vi+s-1 로 구성되는 다각형에 대한 최소삼각형 분할을 구하는 문제를 「정점 vi 에서 시작하는 크기가 s 인 부분 문제」라고 하고, 이후 이를 Si, s 라고 표현하기로 한다. 예를들면 그림 9 (a) 는 S0, 4 이고 그림 9(b) 는 S3, 5 이다. Si, s 를 해결하기 위해서는 다음의 세 경우를 생각할 필요가 있다.
(1) 정점 vi+s-2 를 선택해서 선 (vi, vi+s-1) 및 (vi, vi+s-2) 와 변 (vi+s-2, vi+s-1) 로 삼각형을 구성하여 부분 문제 Si, s-1 를 해결한다.
(2) 정점 vi+1 을 선택해서 선 (vi, vi+s-1), (vi+1, vi+s-1) 과 변 (vi, vi+1) 로 삼각형을 구성하여 부분 문제 Si+1, s-1 를 해결한다.
(3) 정점 vi+k(2 ≤ k ≤ s - 3) 를 선택해서 선 (vi, vi+k), (vi+k, vi+s-1), (vi, vi+s-1) 로 삼각형을 구성하여 부분 문제 Si,k+1 와 Si+k, s-k 를 해결한다.
크기가 3 이하인 부분 문제를 해결하기 위해서는 아무 것도 하지 않아도 되므로, (1) ~ (3) 을 이용해서 어떤 k(1 ≤ k ≤ s - 2) 를 택해서 부분 문제 Si, k+1 와 Si+k, s-k 를 해결하면 되는데, 부분 문제의 분할을 그림 10 에 나타낸다.
그림 10 Si, s 를 부분 문제로 분할
크기가 4 이상인 부분 문제를 해결하기 위해서는 위의 규칙을 이용해서 얻어지는 재귀적인 알고리즘을 사용하기로 하자. 이 때, 크기가 s 이상인 부분 문제를 해결하기 위한 재귀적 호출수만을 세면 모두 3s-4 번이라는 것을 나타낼 수 있으므로, 해결해야 할 부분 문제의 수는 s 를 지수로 한 것이 된다. 문제를 분할한 후의 문제의 크기는 이 재귀적인 절차를 해결하는데 필요한 모든 스텝수와 같은데, 주어진 다각형의 정점수가 n 이므로 문제의 크기는 n 의 지수승이 된다.
그러나, 원래의 문제 이외에는 해결해야 할 부분 문제는 n(n - 4) 종류밖에 없다는 것을 알고 있기 때문에 이 해석이 어딘지 이상하다는 것은 금방 알 수 있을 것이다. 그 부분 문제라는 것은 Si, s(0 ≤ i < n, 4 ≤ s(n) 이므로 재귀적인 절차에서는 같은 부분 문제를 여러 번 해결한다는 것이 분명하다. 예를들면 그림 6 ~ 7 에서 선 (v0, v3) 을 선택하고 그림 9(b) 의 부분 문제에서 v4 를 선택했다고 하면 부분 문제 S4, 4를 해결해야 한다. 그러나, 처음에 변(v0, v4) 를 선택했을 때와 처음에 선(v1, v4) 를 선택해서 부분 문제 S4, 5 를 해결할 때에 v1 과 v4 를 정점으로 하는 삼각형을 완성시키기 위해서 v0 을 선택해도 역시 같은 부분 문제 v4, 4 를 해결하게 된다.
이로부터 삼각형 분할 문제를 해결할 수 있는 효율이 좋은 방법을 얻을 수가 있다. 모든 i 와 s 에 대해 Si, s 를 삼각형 분할하는데 걸리는 시간 (이후, 이것을 Ci, s 로 표현한다) 을 계산하는 표를 만드는 것으로, 이 때 어떤 문제의 해답도 보다 적은 문제의 해답에만 의존하므로 이 표를 크기순으로 메워가면 된다. 즉, 크기 S( = 4, 5, …, n - 1) 에 대해 모든 정점 i 에 대한 문제 Si, s) 의 최소값을 써넣는다. 크기 0 ≤ s < 4 인 문제도 포함해 두면 편리하지만 s < 4일 때 Si, s 의 코스트가 0 이라는 것을 잊어서는 안된다.
여기서 부분 문제를 정하기 위한 Ci, s(S ≥ 4) 를 계산하는 식은 다음과 같다.
Ci, s = min{Ci, k+1 + Ci+k, s-k + D(vi, vi+k) + D(vi +k, vi+s-1)}
여기서 D(vp, vq) 는 정점 vp 와 vq 가 다각형상에서 인접하지 않을 때는 이 두 정점을 연결하는 선의 실이를 나타내고 vp 와 vq 가 인접하고 있을 때는 0 으로 한다.
그림 7 에 있는 다각형과 거리를 토대로 하여 0 ≤ i < 6, 4 ≤ s < 6 에 대한 Ci, s 를 갖는 표를 다음에 나타냈는데, s < 3 인 행에 있는 값은 모두 0 이다. i = 0 인 열과 s = 7 인 행에 C0, 7 의 값이 들어 있는데 이 값은 같은 행에 있는 다른 값과 마찬가지로 다각형 전체의 삼각형 분할을 나타내고 있다. 왜냐하면, 변(v0, v6) 을 보다 큰 다각형의 변이라고 생각해서 그림 7 에 있는 다각형은 큰 다각형의 부분 문제라고 생각하면 된다. 큰 다각형은 v7 에서 v1 까지의 사이에 여러 개의 정점열을 갖고 있을 것이다. s = 7 인 행은 모두 C0, 7 과 같은 값을 갖는다.
7 |
C0, 7 = 75.43 |
|
|
|
|
|
|
6 |
C0, 6 = 53.34 |
C1, 6 = 55.22 |
C2, 6 = 57.54 |
C3, 6 = 59.67 |
C4, 6 = 59.78 |
C5, 6 = 59.78 |
C6, 6 = 63.61 |
5 |
C0, 5 = 37.54 |
C1, 5 = 31.81 |
C2, 5 = 35.45 |
C3, 5 = 37.74 |
C4, 5 = 45.50 |
C5, 5 = 39.98 |
C6, 5 = 38.09 |
4 |
C0, 4 = 16.16 |
C1, 4 = 16.16 |
C2, 4 = 15.65 |
C3, 4 = 15.65 |
C4, 4 = 22.09 |
C5, 4 = 22.09 |
C6, 4 = 17.8 |
s i=0 1 2 3 4 5 6 |
|||||||
예를 들면 i = 6 인 열과 S = 5 인 행의 값 38.09 를 계산하는 방법을 설명하기로 하자. Ci, s 의 계산식에 의해 이 값 C6, 5 는 k = 1, 2, 3 에 대응하는 세 개의 합중에서 가장 적은 값이다. 세 개의 합이라는 것은,
C6, 2 + C0, 4 + D(v6, v0) + D(v0, v3)
C6, 3 + C1, 3 + D(v6, v1) + D(v1, v3)
C6, 4 + C2, 2 + D(v6, v2) + D(v2, v3)
이다. 계산에 필요한 거리는 정점의 좌표로부터 다음과 같이 구해진다.
D(v2, v3) = D(v6, v0) = 0
(이들은 다각형의 변으로 선은 아니므로 코스트는 0 이다).
D(v6, v2) = 26.08
D(v1, v3) = 16.16
D(v6, v1) = 22.36
D(v0, v3) = 21.93
위의
세 가지의 합은 각각 38.09, 38.52, 43.97 이므로 부분 문제 S6, 5
의 최소값은 38.09 가 되었다. 또, 제일 위에 있는
것이 최소값이므로 이 값을 얻기 위해서는 부분 문제 S6, 2
와 S0,
4 를 사용해야 한다는 것 즉, 선 (v0,
v3) 을 선택해서
S6, 4 에는 선 (v1, v3)
을
선택하는 것이 좋다.
위의
표는 최소삼각형 분할의 코스트를 나타내고 있지만 이것으로 삼각형 분할의 방법
자체를 금방 알 수 있는 것은 아니다. 각 Ci,
s 에 대해 위의 식에서 최소값을 만든 k 의 값을
알 필요가 있는데, 이것을 알면 답속에 선 (vi,
vi+k) 와 (vi+k, vi+s-1)
이
포함된다는 것을 알 수 있다(단, k = 1 과 k
= s - 2 일
때는 한쪽이 선이 되지 않는다). 이외의 선은 Si,
k+1 과 Si+k, s-k 의
답에서 생기는데 표에 있는 각 요소를 계산할 때에 최적해의 근거가 되는 k
의
값도 기록해 두면 도움이 된다.
그림 6 ~ 7 에 있는 다각형에 대한 최소삼각형 분할을 그림 6 ~ 11 에 나타낸다.
앞의 표에서 그림 6 ~ 7 의 문제 전체의 답을 나타내고 있는 요소 C0, 7 은 k = 5 일 때에 생기므로 문제 S0, 7`은 S0, 6 과 S5, 2 로 나눠진다. S0, 6 은 6 개의 정점 v0, v1, …, v5 를 가진 문제이지만 S5, 2 는 코스트 0 인 명백한 문제이다. 따라서 코스트 22.09 인 선 (v0, v5) 를 사용하게 되어 다음은 S0, 6 을 해결해야 한다.
C0, 6 의 최소값은 k = 2 인 항에서 생기므로 문제 S0, 6 이 S0, 3 과 S2, 4 로 나누어진다. S0, 3 은 삼각형 v0, v1, v2 이고 S2, 4 는 사각형 v2, v3, v4, v5 이다. 여기서, S0, 3 은 해결할 필요는 없지만 S2, 4 는 해결해야 하고 여기서 선 (v0, v2) 와 (v2, v5) 의 코스트 17.89 와 19.08 이 더해진다. C2, 4 의 최소값은 k = 1 일 때에 생기므로 부분 문제 S2, 2 는 S3, 3 이 얻어지지만 어느 쪽도 정점수가 3 이하이므로 코스트는 0 이 된다. 여기서 선 (v3, v5) 가 도입되는데 이 선의 코스트는 15.65 이다.
분할 통치법은 알고리즘의 전략으로서는 약간 특이한 것으로서 이것은 상황이 잘 파악된 부분을 넓혀감으로써 서서히 해답에 가까워진다는 방식이다. 이런 방식에서는 해답에 접근해 가는 방법에 따라 능률이 좋아지기도 하고 나빠지기도 한다. 예를들면 선형 탐색과 2진 탐색은 목표로 하는 레코드에 어떻게 접근할 것인가가 다르기 때문에 효율에 큰 차이가 생기는데, 선형 탐색에서는 레코드에 한 발씩 접근하고, 2 진 탐색에서는 n / 2, n / 4, n / 8, … 의 폭으로 대담하게 접근한다.
해답에 접근하는 방법은 문제마다 여러 가지가 있는데 이들을 분류하는 것은 어렵지만 일반적인 전략도 많이 알려져 있다. 탐욕법 (greedy algorithm) 은 그중에서 가장 단순한 것으로 현재의 상황에서 국소적으로 보아 가장 좋은 경우를 택해서 나아가는데, 그외의 경우를 무시함으로써 능률의 향상을 기대할 수 있다. 예를들면 앞에서 설명한 Dijkstra 알고리즘과 Prim 알고리즘은 현재 갖고 있는 지식을 이용해서 길이가 가장 짧은 경로 또는 변을 택하기 때문에 탐욕법의 알고리즘으로 분류된다.
탐욕법의 본질적인 문제점은 국소적인 관점에서 가장 좋은 선택이 대국적인 관점에서 보았을 때도 좋은 선택이라는 보증이 없다는 것이다. 즉 눈앞의 이익에 급급해서 큰 이익을 놓칠 우려가 있다. 그러나 문제에 따라서는 국소적인 최선과 대국적인 최선이 일치하는 경우가 있는데 그러한 경우에는 매우 유효한 기법이다. 위에서 설명한 두 가지 알고리즘이 경우 대국적인 최적해를 이 방법으로 구할 수 있다는 것은 각각 이미 증명된 대로이다.
탐욕법에서는 항상 대국적인 관점에서는 최적해를 얻을 수 있다고는 할 수 없는데, 인생과 마찬가지로 「욕심」이란 지금 당장은 좋은 결과를 얻을지 모르나 전체로서는 나쁜 결과를 초래할지도 모른다. 예로서 Dijkstra 알고리즘과 Kruskal 알고리즘에서 변의 무게가 음인 경우가 있을 때는 어떻게 되는지를 상기해 보자. 음의 무게를 가진 변이 존재하는 경우에는 Kruskal 의 최소목 알고리즘에는 영향이 없으므로 최소목을 제대로 구할 수 있지만, Dijkstra 알고리즘은 경우에 따라 최단 경로를 구하지 못하는 경우가 있다.
그림 12 음의 무게를 가진 그래프
예를들어
그림 12 와 같은 그래프에서는 b 와 c 사이에
음의 무게를 가진 변이 있다. 출발점을 s 로 해서 Dijkstra 알고리즘을
적용하면 우선 a 까지의 길이가 1 인 최단 경로를 구하게 된다.
다음은 s 와 a 에서 b 와
c 로 향하는 변만을 조사하므로 b 가 s
에
가장 가깝다고 생각한다. 이 「최단 경로」는 s → a
→ b 로
길이는 3 이다. 그 후에 s 에서 c 로의 최단
경로의 길이가 1 이라는 것을 알게 된다.
그러나
c 를 택하기 전에 b 를 선택한 「욕심많은」선택은
넓은 시야에서 보면 잘못된 것이다. s → a →
c → b 라는
경로의 길이는 2 이므로 b 의 최단 거리가 3 이라는 것은 잘못되었다.
문제에
따라서는 최적해를 구하는 탐욕 알고리즘이 존재하지 않을지 모르지만 상당한 확률로
최적해에 가까운 답을 구하는 탐욕 알고리즘이 존재하는 경우가 있다. 대개는 최적해보다도
수 퍼센트 정도 코스트가 커도 관계없다. 이와 같은 경우 최적해에 가까운 답을
구하는 보다 빠른 방법이 탐욕 알고리즘이 되는 경우도 많다. 모든 경우를 조사하지
않으면 최적해가 구해지지 않는 문제라면 탐욕 알고리즘과 그외의 발견적인 방법을
사용해서 (최적해가 아닐지도 모르지만), 최적해에 가까운 답을 구하는 것이 보다
현실적이다.
최적해를
구하기 위해서는 모든 가능성을 조사해야 하는데, 그렇게 되면 입력의 크기를 지수로
하는 시간이 걸린다는 유명한 문제 (순회 세일즈맨 문제) 를 소개하기로 하자.
순회 세일즈맨 문제 (traveling salesman problem, 이후 「TSP」라고 한다) 란 변에 무게가 할당된 무방향 그래프에서 변의 할당된 무게의 합이 가장 적은 폐로 (모든 정점을 단 한번만 포함하는 폐로) 를 구하는 문제이다. 이러한 폐로를 해밀턴 폐로(hamilton cycle) 라고 한다.
그림 13 에 순회 세일즈맨 문제의 한 예를 나타냈는데 이 그래프에는 정점이 6개 있다. 각 정점의 좌표가 주어져 있으므로 변의 길이를 그 변의 무게라고 한다. TSP 에서는 일반적으로 대상이 되는 그래프를 모든 두 정점 사이에 변이 존재하는 완전 그래프라고 가정하는데, 변의 무게가 유클리드의 거리가 아닌 일반적인 경우에는 존재하지 않는 변은 무게가 무한 대라고 생각하면 된다.
그림 13 순회 세일즈맨 문제의 예
그림 13 에 있는 6 도시를 순회하는 네 가지 폐로의 예를 그림 14 에 나타낸다. 그들 각 폐로의 길이는 52.13, 49.73, 48.39, 49.78 로 그림 6 ~ 14 에 나타낸 폐로 중에서 (c) 가 가장 짧다.
그림 14 폐로의 예
TSP 에는
실용적인 응용이 몇 가지 있는데, 이름이 나타내는 바와 같이 여러개의 지점을 방문하고
나서 출발점에 되돌아오는 코스를 정하는데 사용할 수 있다. 예를들면 우편 배달부가
다니는 코스는 TSP 를 사용해서 정할 수 있는데 이 경우 각 정점은 우체통의 장소를
나타내고 변의 코스트는 두 정점간의 이동 시간을 나타낸다.
TSP 에
대한 탐욕 알고리즘으로서는 kruskal 알고리즘의 변형을 생각할 수 있다. Kruskal
알고리즘과 마찬가지로 우선 가장 짧은 변을 선택한다. Kruskal 알고리즘에서는 선택하려는
변을 추가하더라도 폐로가 구성되지 않는 변을 하나씩 확정했다. TSP인 경우에는
선택하려는 변을 추가했을 때,
(1) 차수 (degree: 정점에 연결된 변의 수) 가 3 이상인 정점이 되지 않고,
(2) 폐로가 구성되지 않는 (단, 선택한 변의 수가 주어진 문제의 정점수와 같은 경우는 제외) 변을 확정한다.
위의
두 가지 조건을 이용해서 차례대로 변을 선택하면 서로 연결되어 있지 않은 경로가
여러 개 구성되고, 마지막 스텝에서 남은 하나의 경로가 닫혀서 폐로가 된다.
예를들면,
그림 13 에서는 변 (d, e) 가 길이 3
으로
가장 짧으므로 우선 이것을 선택한다. 다음은 길이가 5 인 변 (b,
c), (a, b), (e,
f) 를 조사하는데 이들의 순서는 아무래도 좋다. 세 개 다 조건을
만족하고 있으므로 탐욕 방법을 사용하면 세 개를 모두 확정해야 한다. 그리고 나서
남는 변 중에서 가장 짧은 것은 (a, c)
로
그 변의 길이는 7.08 이다. 그러나 변 (a, c)
는
(a, b) 및 (b, c)
와
함께 폐로를 형성하므로 확정할 수 없다. 마찬가지로 다음의 변 (d,
f) 도 버린다. 다음에 변 (b, e)
를
조사하지만 이 변을 추가하면 b 와 e 의
치수가 3이 되어 버리므로 지금까지 선택한 변과 합해도 폐로가 되지 않기 때문에
확정할 수 없다. 마찬가지로 (b, d)
도
버린다. 다음에 (c, d) 를 선택하면 a
→ b → c → d
→ e → f 라는
하나의 경로가 구성되는데, 이 경로에 마지막으로 (a, f)
를
선택해서 추가하면 그림 15 와 같은 폐로가 완성된다.
그림 15 순회 세일즈맨 문제의 답
어떤 문제의 최적해를 구하려고 하지만 모든 가능성을 조사하지 않고는 최적해를 얻을 수 없는 경우가 있다. 여기서는 모든 가능성을 조직적이고도 효율적으로 조사할 수 있는 기법인 백트랙킹법 (backtracking) 을 소개하기로 한다.
게임
목 (game tree) 과 식 변형 목 등을 완전한 나무의 형태로 만들어서 컴퓨터에 기억시킬
수는 없다. 예를들면, 장기라던가 바둑에서는 경우의 수가 너무 많아서 이들을 전부
기술해서 한꺼번에 컴퓨터에 기억시키는 것은 불가능하기 때문이다. 그러나, 이들
나무는 구조가 매우 규칙적이다. 즉, 하나의 정점 (정점은 경우, 수식, 논리식 등을
나타낸다) 에서 어느 정점으로 변이 접해 있는가가 여러 개의 규칙에 의해 명확하게
정해져 있으므로 나무를 만들어 가면서 조사를 할 수가 있다.
여기서는
백트랙킹을 설명하기 위해 3목이라는 게임을 이용하기로 한다. 3목이란 게임은 두
사람이 그림 16 과 같은 사각형에 바둑돌을 교대로 놓아서 세 개의 돌을 동일 직선상에
먼저 놓는 사람이 이기는 게임이다. 그림 16 에서 각 칸에 쓰여진 번호는 각 칸을
구별하기 위해서 붙여 놓은 식별자이다.
|
① |
② |
③ |
|
④ |
⑤ |
⑥ |
|
⑦ |
⑧ |
⑨ |
그림 16 3 목의 초기 상태
그림
16 과 같이 전혀 바둑돌이 없는 초기 상태에서 출발해서 게임의 진행 상황을 보기
위해 하나의 경로를 따라가 보자. 포석은 기계적으로 「각 칸에 할당된 번호가 적은
순」으로 비어 있는 곳에 교대로 흑과 백을 놓는다. 이 방법을 토대로 그림 17(a)
와
같이 혹은 제일 처음에 왼쪽 위에 돌을 두고, 백은 그 오른쪽 옆에 돌을 두어가면
일곱 번째에서 흑이 승리하게 된다.
이것은
하나의 시행 (trial) 에 지나지 않는다. 이렇게 하면 백이 패하게 되므로 백이 이길
수 있는 경우를 살펴보기 위해 백에 있어서 다른 방법을 모색해 보기로 하자. 이를
위해, 경우 E 로 「돌아와서」(이것을 백트랙 (backtrack) 이라고 한다) 다시 생각해
보면 그림 17(b) 와 같이 E 에서 F′ 로 나아갈 수가 있고, 이하 G′, H, I 로 진행하면
역시 흑이 이기게 된다.
그림 17 시행과 수정
그러면 조금 더 백트랙해서 다시 보기로 하자. G′ 까지 백트랙하면 다른 경로를 발견하게 되는데 (그림 17 (c)), 그쪽 경로를 택해서 나아가면 비길 수 있다.
이러한 『시행과 수정』은 나무의 일부분만을 사용해서 행할 수 있는데, 이처럼 숨겨져서 표면에는 나타나지 않는 나무를 암목적 나무 (implicit tree) 라고도 한다. 암묵적 나무를 그림 18 과 같이 (일부분이긴 하지만) 보이게 그리면 시행과 수정 모습을 금방 알 수 있다. 그림 18 에서 아래로 향하는 변의 게임 진행을 나타내고, 위로 향하는 변은 백트랙을 나타내며, 점선은 지금 단계에서는 아직 조사되지 않는 경로를 나타낸다.
그림 18 E 를 루트로 하는 나무
그림
18 까지 행한 것은 나무상에서의 변을 번호순으로 늘리거나 줄이면서 (백트랙) 각
경우에 도달한 것이다. 여기까지의 단계에서 경우 F 에서는 흑이 승리하고, 경우 G′
에서는
비긴다는 것을 알 수 있다. 이후 경우 F′에서는 누가 이기는가를 알아보기 위해
계속해서 백트랙과 시행을 계속하면 경우 E 에서는 흑이 승리한다는 것을 알게 되고,
최종적으로는 초기 상태 (그림 14 R) 에서는 비긴다는 것을 알게 될 것이다.
여기서
중요한 것은 하나의 경로를 조사할 때는 거기에 나타나는 경우만을 기억해 두면 된다는
것이다. 아직 고려하지 않은 경우와 이전에 고려의 대상이었지만 백트랙킹에 의해
현재의 경로에 포함되지 않는 경우는 잊어 버려도 된다. 이와 같이 함으로써 완전한
나무를 만들어 낼 때보다는 훨씬 적은 기억 용량으로 전체를 계속 조사할 수가 있다.
이러한 「조사」를 능률적으로 행하기 위해서는 조사하지 않아도 되는 부분을 조사 대상에서 제거하면 되는데, 조사 대상을 제거하는 기법으로 α - β 변 제거라는 것이 있으나 여기서는 생략하기로 한다.
해결하려는 문제마다 크기가 다르므로 한마디로는 말할 수 없지만 복잡도가 O(n)이나 O(n log n) 또는 O(n3) 등과 같이 문제의 크기 n 에 대해 제곱승 또는 세제곱승 정도의 복잡도를 가진 알고리즘이라면 실제로 사용가능하다. 제5장까지 설명한 알고리즘은 이 범위에 속하는 「효율적인」알고리즘이었으나 문제에 따라서는 이러한 효율적인 알고리즘이 없는 경우도 흔히 있다.
이와 같이 효율적인 알고리즘이 발견되지 않은 「어려운」문제에 대해서 이론적인 수법을 이용하여 그 어려운 정도를 알아내려는 연구가 오래전부터 많이 행해졌다. 효율적인 알고리즘을 발견해 내지 못하기 때문에, 그 문제에 대해서는 효율적인 알고리즘이 존재하지 않는다는 것을 증명하는 연구를 하는 것은 당연하다.
이러한 이론적인 연구를 복잡도 이론 (complexity theory) 이라고 한다. 알고리즘에 대한 연구는 복잡도 이론에 관한 추상적인 것과 지금까지 설명한 알고리즘 개발을 목표로한 실제적이고 구체적인 것으로 나눌 수 있다.
복잡도 이론에서는 문제를 그 어려운 정도에 따라 분류하는 것이 주요 연구 테마이다. 여기서는 그 분류에 관해서 알려져 있는 사실과 해결되지 않는 문제점을 간단히 소개하기로 한다. 이들 연구의 성과는 효율적인 알고리즘을 설계한다는 목적과는 직접 관계가 없다. 그러나 본질적으로 어려운 문제에 대해서 효율적인 알고리즘을 개발하려는 필요없는 노력을 하지 않게 하고 다른 방향에서 문제를 해결하는 기회를 제공한다는 소극적인 효용이 있다.
복잡도
이론에서는 복잡도가 문제의 크기 n 의 다항식으로 평가되는
알고리즘을 효율적 (efficient) 알고리즘이라고 하고, 반대로 n 의
다항식이 아닌 지수 함수의 형태로 평가되는 알고리즘의 비효율적 (non-efficient)
알고리즘이라고 한다. 다항식과 지수 함수의 사이에 위치하는 알고리즘 (O(nlog n)
과 같은 북잡도를 가진 알고리즘) 에 대해서는
아직 충분히 연구가 되고 있지 않는 실정이다.
효율적인
알고리즘이 존재하는 문제를 쉬운 문제 (tractable problem) 라고 하고 효율적인 알고리즘이
존재하지 않는 문제를 어려운 문제 (intractable problem) 라고 한다.
쉬운 문제와 어려운 문제를 나누는 기준은 모든 경우를 생각해야 하는 것에 있다. 즉 모든 경우를 생각해야 하는 문제를 어려운 문제라고 하고 그렇지 않은 문제를 쉬운 문제라고 한다. 문제가 쉽다는 것을 증명하기 위해서는 효율적인 알고리즘을 개발하면 그것으로 증명이 된다. 반대로 어렵다는 것을 증명하기 위해서는 어떤 알고리즘을 이용하더라도 그 문제를 효율적으로 해결할 수 없다는 것을 증명할 필요가 있기 때문에 그다지 간단하지는 않다. 어렵다는 것이 증명되어 있는 문제는 몇 가지 있지만 그 수는 많지 않다. 이와 같이 다항식 시간의 알고리즘이 존재하지 않는다는 것이 알려져 있는 문제는 그 문제에 대한 효율적인 알고리즘을 개발하려고 할 때 필요없는 노력을 하지 않고 처음부터 포기할 수 있는 결단을 내리는데 도움이 되므로 이러한 의미에서는 다루기 쉽다.
그러나, 이보다 다루기 어려운 것은 쉬운지 어려운지가 (지금까지) 알려져 있지 않는 문제이다. 이들 문제에는 효율적인 알고리즘이 알려져 있지 않을 뿐만 아니라 다항식 시간의 알고리즘이 존재하지 않는다는 것도 증명되어 있지 않다. 그리고 실제로도 어려운 것을 하려고 하면 금방 이들 문제에 부딪힌다고 해도 과언이 아닐 정도로 이런 문제는 매우 많이 존재한다. 이와 같은 문제들을 NP 완전 문제 (NP-complete problem) 라고 한다.
일반적인 알고리즘에서는 각 스텝에서 어떤 조작을 한다는 것이 명확하게 정해져서 기술되어 있으므로 데이터를 입력하면 어떤 조작을 어떤 순서로 한다는 것을 알 수 있다. 이러한 알고리즘을 특히 결정성 알고리즘 (deterministic algorithm) 이라고 부른다. 결정성 알고리즘에 의해 다항식 시간에 해결할 수 있는 문제를 모두 클래스 P(class P) 에 속하는 문제라고 한다.
이에 대해서 NP 라고 하는 것은 비결정성 알고리즘 (nondeterministic algorithm) 을 이용하면 다항식 시간에 해결할 수 있는 것을 의미한다. 비결정성 알고리즘이란 개개의 스텝에서 취할 수 있는 경로가 여러 개로 나눠져 있어서 그 중에서 적당한 경로를 택해서 실행해 나가는 것이다. 경로를 택한다고 하더라도 if 문에 의한 조건 분기와 같이 어느 경로를 선택할 것인가에 대한 정보가 주어져 있는 것이 아니다. 아무튼 어느 경로든지 하나의 경로를 택해서 앞으로 실행해 나가는 수밖에 없다. 그리고 이들 경로 중 가장 적합한 경로를 잘 택했을 때에 다항식 시간으로 답을 찾아내는 문제의 집합이 클래스 NP (class NP) 이다.
그러나, 가장 좋은 경로를 택하면 다항식 시간으로 해결할 수 있다고는 하더라도 그런 경로를 잘 택할 수 있다는 보장도 없다. 어느 경로를 택하면 좋을지를 알 수 있는 방법이 없으므로 잘못된 경로를 택하면 오랜 시간을 필요로 할지도 모르고 답을 찾아내지 못할지도 모른다.
즉 정말도 다항식 시간에 해결할 수 있는 것은 어느 경로를 택하면 좋은지를 알 수 있는 것은 「신 (god)」뿐이다. 신이 아닌 사람이나 컴퓨터로서는 어느 경로를 택해서 앞으로 실행해 나가서 막히면 되돌아오는 등 모든 경로의 계산을 병행해서 나아가는 등의 수단을 사용할 수밖에 없다. 즉, 비결정성 알고리즘의 동작을 일반적인 결정성 알고리즘으로 모방해서 해결하는 셈이다.
이렇게 모방함으로써 복잡도의 정도도 바뀐다. 예를들면, 각 스텝에서 두 개씩 분기한다고 하면 원래의 비결정성 알고리즘인 경우 n 스텝에 해결할 수 있는 문제도 O(2n) 정도의 복잡도를 필요로 한다고 예상할 수 있다.
이상의 설명으로 크래스 NP 에 속하는 문제를 실제로 다항식 시간에 해결할 수 있다고 단언할 수 없다는 것은 이해할 수 있을 것이다.
결정성 알고리즘에 의해 다항식 시간에 해결할 수 있는 문제는 비결정성 알고리즘에 의해서도 다항식 시간에 해결할 수 있으므로 P ⊆ NP 가 성립한다. 그러나 NP ⊆ P 즉 NP 에 속하는 어떤 문제라도 다항식 시간에 해결할 수 있다면 P = NP 가 성립한다. 이것이 사실인지 아니면 P = NP 즉, 다항식시간에 해결할 수 있는 알고리즘이 존재하지 않는 문제가 NP 속에 있는지는 대문제이다. 이 문제는 P = NP 문제라고 불리는 문제로서 컴퓨터 과학 분야에서는 최대의 과제 중 하나이다.
많은 연구자는 P ≠ NP 즉, NP 속에는 효율적으로 해결할 수 없는 문제가 있다고 믿고 있다. 이것은 효율적인 알고리즘이 존재할 것같지 않은 문제가 NP 속에 많이 존재한다는 점과 비결정성을 그렇게 간단하게 결정성 알고리즘으로 바꿀 수 있다고는 생각하지 않는다는 등의 이유 때문이다. 그러나 아직 증명은 되지 않는 상황이다. 그러나 아직 증명은 되지 않는 상황이다.
NP-hard 문제란 NP 에 속하는 어떤 문제보다도 어렵거나 같은 정도로 어려운 문제를 말한다.
NP 완전 또는 NP-hard 문제에 대해서 현재 알려져 있는 알고리즘의 복잡도는 최악의 경우 입력 크기에 대해 지수 함수가 된다. 그래서 NP-hard 라는 것이 알려져 있는 최적화 문제에 대해서 구하는 답이 반드시 최적해가 아니라고 하더라도 최적해에 가까운 것이면 된다. 그러나 답을 출력할 때까지의 시간은 다항식 가능하다면 O(n) 또는 O(n2) 정도로 하는 것이 바람직하며 실용적으로는 이것으로 충분한 경우가 있다. 이와 같이 최적해에 가까운 답을 근사해라고 하고 그것을 구하는 (결정성) 알고리즘을 근사 알고리즘 (approximation algorithm) 이라고 한다.
근사 알고리즘을 평가하는 척도로는 일반적인 알고리즘과 마찬가지로 시간 복잡도와 영역 복잡도 이외에 그 알고리즘에서 얻어지는 답이 최적해에 어느 정도 가까운가를 평가하는 정밀도 (accuracy) 라는 것이 있다. 물론 정밀도와 복잡도면에서 모두 뛰어난 알고리즘이 있으면 가장 바람직하지만, 그렇지 않은 경우에는 정밀도는 좋지만 효율이 좋지 않은 알고리즘과 효율은 좋으나 정밀도가 나쁜 알고리즘을 문제의 상황에 따라서 잘 나눠서 사용할 필요가 있다.
여기서 다루려고 하는 문제는 순회 세일즈맨 문제에 다음과 같은 제한을 추가한 문제이다 (정점 x 와 y 를 연결하는 변의 무게 (길이) 를 dxy 라고 표현한다.)
(1) 그래프상에 있는 각 변의 길이는 0이상
(2) 그래프상에 있는 임의의 세 정점 A, B, C 에 대해서, dAB + dBC ≥ dAC
첫 번째 조건은 임의의 한 정점에서 다른 정점을 방문했을 때, 도리어 값이 줄어 드는 경우는 없다는 것을 의미한다. 그리고, 두 번째 조건은 정점 A 에서 정점 C 를 방문할 때 정점 B 를 통해서 가는 것보다도 직접 가는 쪽이 좋다는 것을 의미한다. 이 식을 삼각 부동산이라고 한다.
이들 두 조건은 실제의 문제에 적용하는 상황을 생각하면 매우 자연스러운 조건이다. 이들 조건을 추가했을 때의 순회 세일즈맨 문제를 유클리드적 순회 세일즈맨 문제 (Euclidean traveling salesman problem) 라고 한다. 여기서는 그래프의 정점 수는 n 이라고 하고 변의 개수는 n(n - 1)/2 라고 한다. 이 문제의 경우에는 모든 두 정점 사이에는 변이 존재한다는 점을 주의해야 하는데, 변이 없다는 것은 dAB = ∞ 라고 해석할 수 있지만 이것은 두 번째 조건에 어긋난다.
위의 문제를 해결할 수 있는 가장 단순한 알고리즘 (단순 탐욕법) 을 소개하기로 한다.
우선 임의의 한 정점 (u 라고 한다) 을 택하고 정점 u 에 연결되어 있는 변 중에서 무게가 가장 적은 변 ((u, v) 라고 한다) 을 택해서 정점 v 로 이동한다. 이번에는 정점 v 에 연결되어 있는 변 중에서 무게가 가장 적은 것을 택하는데, 이 때 정점 v 에서는 변 (v, u) 를 대상에서 제외한다. 이와 같이 각 정점에서 무게가 가장 적은 변 (이미 지나온 정점으로 향하는 변을 제외) 을 선택하는 조작을 반복해서 마지막에 정점 u 에 되돌아 오게 되면 이것이 하나의 답이 된다.
그러나, 이 방법은 정밀도가 그다지 좋지 않으며, 얻어지는 경로의 길이가 최악의 경우에 최적해의 O(log n) 배나 되는 경우가 있다. 그러나 실제적인 순회 세일즈맨 문제의 경우에는 이와 같은 단순한 방법으로도 충분한 경우가 있다는 것이 알려져 있다.
다음은 이 알고리즘을 평가하기로 한다.
각 정점에서는 그 정점에 인접해 있는 변을 한번씩 조사하는데, 이 때 지금까지 지나온 정점으로 되돌아 가는 것을 제외한 변 중에서 가장 적은 변을 구한다. 각 정점에 인접해 있는 변의 개수는 n - 1 이므로 전체 복잡도는 O(n2) 이 된다.
이외에도 삽입법이라든가 최소목법 등의 방법을 이용하면 정밀도가 높은 답을 구할 수 있는데, 이들 방법에 대해서는 생략하기로 하고, 참고 문헌을 참고로 하기 바란다.