최적화 문제 (p. 165)

답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 ‘좋은’ 답을 찾아 내는 문제들을 통칭해 ‘최적화 문제(Optimization Problem)라 한다. 예를 들어, n개의 원소 중에서 r개를 순서없이 고르는 방법은 답이 딱 1개밖에 없으니 최적화 문제가 아니지만, n개의 사과중에서 r개를 골라 무게의 합을 최대화하는 문제는 최적화 문제가 된다.

최적화 문제를 해결하는 방법은 여러가지가 있으나, 그 중 가장 기초적이고 직관적인 방법이 완전탐색(Exaustive Search)이다. 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문이다.

가장 유명한 최적화 문제중 하나는 TSP(Traveling Salesman Problem) 문제가 있다. 각 노드를 한번씩 방문하고, 시작노드로 되돌아가는 가장 짧은 경로를 찾는 것이 TSP문제이다.

완전탐색으로 문제를 풀기#

1. 시간 안에 답을 구할 수 있을지 확인하는 것 시작 노드로 돌아오는 최단 경로를 찾는 것이기 때문에 아무 노드를 시작 노드로 잡아도 된다. 그래서 0번 노드부터 출발한다 가정하면 남은 노드들을 어떤 순서로 방문할지 결정하기만 하면 된다. 따라서 남은 N-1개의 노드를 나열하는 방법의 수는 $(N-1)!$이다. N=10이면 9! = 362,880으로, 컴퓨터로는 1초도 걸리지 않는다.