10개 도시를 최단 거리로 여행하는 법(지수, 다항 시간 알고리즘)

-지수 알고리즘

-다항 시간 알고리즘

 

알고리즘 대표적인 두가지 기준은 시간과 공간에 의한 복잡도이다.

외에 다른 복잡도를 갖는 알고리즘도 있는데

지수시간(Exponential-Time)과 다항시간(Polynomial-Time)이 있다.

 

지수시간(Exponential-Time) 알고리즘

반복문의 수행 횟수가 2^N의 지수식으로 표현 -> 지수 시간 알고리즘

지수 시간은 가장 큰 수행 시간 중 하나.

 

- 일의 양이 빠르게 늘어남.

 

- 한 개의 항목이 추가되면 수행해야 할 일의 양이 2배2^N의 비율로 증가.

   logN(이진 탐색)에서는 항목의 수를 2배로 늘려도 일의 단계는 1개만 늘어나

   한편으론 지수 시간 알고리즘은 logN(이진 탐색) 알고리즘과 정반대라고 볼 수 있음.

 

- 모든 가능한 경우를 하나씩 시도해 봐야만 하는 상황에서 사용됨.

ex) 암호 기법

   :  지수 시간 복잡도를 갖도록 하는 데 기반을 두는데 누군가 암호를 해독하기 위해서는 일일이 모든 경우의 수를 봐야 하        기에 큰 N(긴 암호)을 갖는다면 암호 해독 확률이 희박하므로 적의 공격을 방지할 수 있다.

 

 

다항 시간(Polynomial-Time) 알고리즘

 

반복문의 수행 횟수가 입력 크기의 다항식으로 표현되면 다항 시간 알고리즘이라 하며, 두 가지 나뉨.

 

1. 결정적 알고리즘(Deterministic Algorithm)

2. 비결정적 알고리즘(Nondeterministic Algorithm).

 

1) 결정적 알고리즘(Deterministic Algorithm)

특정한 값을 입력에 따라 정해진 값이 나오는 것을 결정적 알고리즘.

ex) 수학 공식

   :   f(x) = x+1이라고 한다면 f(1) = 2, f(2) =3, f(k) = k+1

      정해진대로 결과의 값 출력.

 

2) 비결정적 알고리즘(Nondeterministic Algorithm)

동일한 값을 입력해도 다른 결과를 출력할 수 있다고 정의할 수 있음.

결정적 / 비결정적 알고리즘

 

 

P  vs NP

이론적 복잡도 종류와 관련 용어.

복잡도 종류

: 계산 복잡도 이론에서 계산 복잡도에 따라 문제를 분류한 것.

 

-복잡도 종류의 정의-

추상기계 M이 O(f(n)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (n은 입력의 길이).

 

즉, 문제의 난이도와 같은 쉽니? 어렵니?에 따라 구분한 것이며, 문제가 쉽다는 것은 짧은 시간 내에 문제를 풀 수 있다는 것이고, 그렇지 않은 문제는 어려운 문제라는 것이다.

 

1. 'P(Polynomial-time)' 문제

: 다항 시간(Polynomial-Time) 알고리즘으로 풀리는 결정적 문제(Decision Problem)의 집합.

 

- 결정적 문제는 Yes/No로 대답할 수 있는 문제며, 답을 찾는 걸리는 시간이 짧은 문제로 즉, 쉬운 문제이다.

 

- '결정적'이라는 것은 계산 단계에서 하나의 가능성만을 고려하면 되는 것이다.

그러므로 하나의 input에서는 하나의 output만 나올 수 있다.

 

 

2. 'NP(Non-deterministic Polynomial-time)' 문제

: 비결정적 다항 시간(polynomial-time nondeterministic) 알고리즘으로 풀리는 결정 문제(decision problem)의 집합.

- 비결정적 알고리즘은 결정적 알고리즘과는 다르게 매 단계 여러가지 가능성이 존재함. 그러므로 하나의 input에 대해서 다른 output이 나올 수가 있음.

 

- 간단하게 NP를 설명하자면, 풀기는 어려울 수 있지만, 답이 맞는지 확인하기는 쉬운 문제라는 의미로 보자.

 

 

 

 

 

 

P / NP 포함 관계

 

10개 도시를 최단 거리로 여행하는 법 (여행하는 외판원 문제)

-> NP 문제의 대표적인 예

 

외판원은 자신이 사는 도시에서 출발해 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와야 하고, 여기서 목표는 각 도시를 정확히 한 번씩(반복 없이) 방문하며, 전체 여행한 거리를 최소로 만드는 것.

최근접 이웃 해법으로 풀이한 문제

첫 번째 풀이는 직관적으로 와 닿는 '최근접 이웃' 휴리스틱으로 찾은 해법.

한 도시에서 시작해 아직 방문하지 않은 도시 중 가장 가까운 도시로 이동하는 방식임. (여행의 총 거리 12.92)

(시작하는 도시가 바뀌면 여행 경로가 바뀔 수도 있다는 점 주의)

 

 

최상의 해법으로 풀이한 문제

두번째 풀이는 모든 가능한 경로를 시도한 방법.

약 18만 개 경로 전체를 완전 탐색해서 찾은 최단 경로. (여행의 총 거리 11.86)

(최근접 이웃 경로의 최단 거리보다 약 8% 짧다.)

 

 

완전 탐색하는 것이 효율적인 방법이라 본다.

컴퓨터 과학자들이 말하는 복잡도란 대부분 최악의 경우(worst case)에 대한 것이겠지만,

보통은 최악의 경우까지 가지 않음. 어떤 문제(예를 들면 암호문제)는 답을 계산하는 데 극한의 시간이 필요하겠지만

모든 문제를 그렇게 난해하게 접근할 필요는 없다.

실제 상황에서는 대부분 근사치만 구하는 것으로도 충분할 수 있다. 완전히 최적인 해법을 구할 필요는 없다.