현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요?
아시는 분들은 아시겠지만, 컴퓨터가 모든 것을 해결해 줄 수는 없습니다. 가장 유명한 예시로는 halting problem이 있습니다. 이는 어떤 컴퓨터 프로그램과 그 프로그램의 한 입력이 주어졌을 때, 프로그램이 언젠간 끝이 나는지 아니면 영원히 동작할지를 판단하는 문제입니다. 저명한 수학자 Alan Turing은 이 문제가 컴퓨터로는, 좀 더 정확히는 Turing machine으로는, 해결할 수 없다는 것을 증명하였습니다.
이번에는 약간 결이 다른 이야기를 해보겠습니다. 여러분들이 유명 밴드의 매니저라고 생각해 보겠습니다. 전국 투어를 기획하고 있는 단계입니다. 어떤 지역을 갈지는 이미 다 정해졌습니다만, 어디를 어떤 순서대로 갈지가 아직 정해지지 않았습니다. 밴드 구성원들의 컨디션을 위해서나 예산의 이유에서나 지역 사이의 이동 거리를 최소화하고 싶을 것입니다. 과연 어떤 순서대로 지역을 방문하면 가장 좋을까요?
이미 눈치를 채신 분들도 계실 것입니다. 앞의 문제는 매우 유명한 traveling salesman problem(TSP)입니다. 이 문제에서는 방문해야 하는 도시들과 도시 사이를 이동할 때 들어가는 비용이 입력으로 주어집니다. 우리의 목표는 출발 지점에서 모든 도시를 정확히 한 번씩만 방문하여 다시 출발한 지점으로 되돌아오는 경로 중 비용이 가장 적게 드는 것을 찾는 것입니다.
이 문제는 컴퓨터로 해결할 수 있습니다. 가장 간단한 (하지만, 멍청한) 방법은 모든 도시의 순열(permutation)에 대해서 비용이 얼마큼 나오는지를 계산한 후 가장 작은 비용을 주는 경로를 하나 선택하는 것입니다. 근데, 도시의 개수가 적다면 모르겠지만, 모든 순열을 고려한다는 것은 그냥 풀지 않겠다는 말과 같습니다. 당장에 도시가 12개만 넘어가도 억 단위의 경우의 수를 고려해야 합니다. 그렇다면 이 문제를 효과적으로 해결하는 방법이 존재할까요? 여기서 제가 말씀드리는 ‘효과적’이라는 말은 입력의 ‘다항 시간’에 문제를 해결하는 방법이 존재하느냐입니다.
안타깝지만, 모릅니다. 그리고 더욱 안타까운 점은 아무래도 없을 것 같다는 것입니다. 왜냐하면, TSP는 잘 알려진 NP-난해(NP-hard) 문제 중 하나이기 때문입니다. 이는 P=NP가 아닌 이상에야 이 문제를 효율적으로, 즉, 다항 시간에 해결하는 알고리즘은 존재하지 않습니다. 이에 대해 궁금하신 분들은 다음을 참조하시기 바랍니다.
2020/09/08 - [수학적 도구/Theory of computation] - P vs NP 쉽게 이해하기
컴퓨터로는 가망이 없으니 손으로 직접 풀어야 할까요? 그것도 그리 쉬워 보이지는 않습니다. 결국, 컴퓨터를 사용하기는 해야 할 것인데, 어떻게 사용해야 할까요? 우리에게 주어지는 선택지는 다음 세 가지입니다.
1. 입력을 포기한다. 즉, 모든 입력이 아니라 자그마한 입력에 대해서만 고려한다는 것입니다. 앞의 예시에 적용하면, 도시의 개수가 5~6개밖에 되지 않는 상황만을 고려한다는 것입니다. 이때는, 모든 경우의 수가 그렇게 많지 않을 것이므로 빠른 시간에 최적해를 얻을 수 있을 것입니다.
2. 시간을 포기한다. 즉, 다항 시간 복잡도를 포기한다는 의미입니다. 그렇다고 앞에서 설명한 brute-force 방법만을 취하겠다는 뜻은 아닙니다. 어떤 도시의 순열을 고려하고 있을 때, 만약 그 순열이 영 가망이 없어 보이면 그 순열과 비슷한 순열은 나중에 보는 식으로 똑똑하게 찾아볼 수도 있을 것입니다. 그러한 intelligent search도 포함하는 내용입니다.
3. 최적해를 포기한다. 대신, 모든 입력에 대해서 빠른 시간에 결과를 도출해야 할 것입니다. 그러면서도 결과는 그다지 나쁘지 않아야 할 것입니다.
여기서 마지막 항목에 주목하시기 바랍니다. 만약 우리가 모든 입력에 대해서 다항 시간에 결과를 도출하는데, 그 결과가 나빠 봐야 최적해보다 “약간” 안 좋다면 그 방법은 실생활에서 매우 요긴하게 사용될 것입니다. 이것이 바로 근사 알고리즘(approximation algorithm)입니다.
\( \rho \)-approximation algorithms
어떤 minimization problem에서 \(\rho\)-approximation algorithm은 모든 입력 \(\mathcal{I}\)에 대해서 다음을 만족하는 알고리즘을 말한다.
1. 다항 시간에 동작한다.
2. \(\mathsf{OPT}_\mathcal{I}\)를 입력 \(\mathcal{I}\)의 최적해의 비용,\(\mathsf{SOL}_\mathcal{I}\)을 이 알고리즘의 결과의 비용이라고 할 때, \(\mathsf{SOL}_\mathcal{I} \leq \rho \cdot \mathsf{OPT}_\mathcal{I}\)
만약 bipartite matching과 같이 maximization problem이라면, 반대로 \(\mathsf{SOL}_\mathcal{I} \geq \rho \cdot \mathsf{OPT}_\mathcal{I}\)가 되어야겠지요. 이때의 \(\rho\)를 우리는 근사비(approximation ratio)라고 부릅니다.
그렇다면, TSP를 해결하는 좋은 근사 알고리즘이 존재할까요? 슬프게도 임의의 입력에 대해서는 근사 알고리즘이 존재하지 않는다는 것이 알려져 있습니다. (증명: 임의의 그래프에 Hamiltonian cycle이 존재하는지 판단하는 문제가 이미 NP-hard합니다. 이 문제를 임의의 입력을 받는 TSP의 아무 근사 알고리즘으로 해결할 수 있습니다.) "뭐가 이렇게 안 되는게 많아?"라고 생각하실 수 있다고 생각합니다. 하지만 문제에 약간(?)의 제약 조건을 추가하면 좋은 근사비를 가지는 알고리즘을 만들 수 있습니다. 이는 차근차근히 알아가 보도록 하겠습니다.
지금까지 근사 알고리즘이 무엇인지에 대해서 알아보았습니다. 컴퓨터는 세상의 모든 문제를 해결할 수 없을 뿐더러, 어떤 문제들에 대해서는 해결할 수는 있어도 (아마도) 합리적인 시간에 효과적으로 해결하지 못합니다. 그때는 우리가 양보를 해야겠죠. 하지만 너무 양보하고 싶지는 않을 것입니다. 우리가 이 정도만 양보하고도 빠른 시간에 결과를 도출할 수 있는가? 아니면, 아무리 못해도 이 정도는 양보를 해야만 빠른 시간에 결과를 도출할 수 있는가? 이 질문에 대한 답을 내리는 것이 근사 알고리즘을 공부하는 것의 핵심입니다. 다음부터는 몇 가지 잘 알려진 간단한 근사 알고리즘부터 기회가 된다면 최신의 재미있는 근사 알고리즘도 다뤄보고자 합니다.
감사합니다.