[cs] 10개 도시를 최단거리로 여행하는 법

지수 알고리즘

• 문제 한 가지를 형식적으로 줄여 나가 2개 혹은 더 많은 부분의 더 작은 사이즈의 문제들로 만드는 알고리즘

• 사실상 실행 가능한 모든 경우의 수를 하나씩 시도

• 암호 기법에 사용되는 알고리즘은 특정 계산 과제를 수행하는 일이 지수 복잡도를 갖도록 하는데 기반을 둠. 지름길을 모르고서는 문제를 바로 푸는 일이 계산상 실행 불가능할 정도로 큰 N을 선택하여 적의 공격 방지

NP문제

• 각 단계에서 여러가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘으로 다항시간내에 문제를 해결할 수 있는 문제

여행하는 외판원 문제

• 조합 최적화 문제의 일종으로 NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례

• 다항 시간에 이 문제를 해결할 수 있는 해결책이 없어 지수 시간에 풀 수 있다.

• 최근접 이웃이라는 풀이법으로 가장 가까운 곳을 지나쳐 가는 것과 최단 거리의 풀이법이 얼마 차이나지 않아 실생활에서는 근사치를 구하는 것만으로도 최적인 해법을 구할 필요는 크게 없다.