* 최단경로찾기란?
- 우리가 흔히 접하는 핸드폰의 지하철 안내도, 자동차의 네비게이션 등은 모두 최단거리 알고리즘을 사용하여서
작동을 한다. 내가 소개하려는 최단 경로도 있지만 요즘은 A*라는 최단 경로 알고리즘이 많이 쓰인다.
- 지금 소개하려는 Floyd알고리즘을 이해하려면, 그래프에 대한 이해가 이미 충분히 되있어야 할 것이다.
* 최단경로를 풀기위해 알아야하는 용어
- 가중치 행렬 W[i][j]
> 정점 i에서 j로 이동하는 화살표가 존재한다면 화살표에 해당하는 가중치
> 정점 i에서 j로 이동하는 화살표가 없다면 무한대
> 정점 i와 j 의 값이 같다며느 0의 값을 가진다.
- 경로비용 : 경로상의 모든 화살표들의 가중치들의 합
- 최단경로 : 경로비용이 가장 작은 경로
- 최단 경로 문제는 최적화(optimization)문제에 속한다.
> 최적화 문제란? 주어진 문제에 대하여 하나 이상의 많은 답이 존재 할때, 이중에서 가장 최적인 답을 찾는 문제
ex)
> v1 ~ v4까지 가는 경로 비용
v1 - v2 - v3 - v4 : 8
v1 - v2 - v4 : 3
v1 - v4 : 1 (최단경로!!)
* 무작정 알고리즘(brute-force Algorithm)
- 한 정점에서 다른 정점으로 가는 모든 경로의 비용을 구한뒤, 그들중의 최소 경로를 찾는다.
- 분석
> 그래프가 n개의 정점을 가지고 있고, 모든 정점들 사이에 화살표가 존재한다고 가정하자. 그러면 한 정점
Vi에서 다른 정점 Vj로 가는 경로들을 다 모아 보면 그 경로들 중에서 나머지 모든 정점을 꼭 거쳐 가는
경로만을 우선적으로 생각해보자.
(ex) 정점이 v1~v5까지 있을때 v2에서 v3으로 가는데 v1,v4, v5를 모두 거차가는 경우)
> n개의 정점이 있을때 Vi에서 출발하여 처음에 도착할 수 있는 정점의 개수는
n-2(n개에서 시작점, 도착점 제외)개 이다. 그 중에 하나를 선택하여 다음에 도착 할 수 있는 정점의 개수는
n-3개이다. 이렇게 계속 반복하다 보면 총 비교해야될 원소의 개수는 (n-2)*(n-3)*...*2*1 = (n-2)!이다.
> 모든 경로가 아닌 특정 경우만해도 (n-2)!개의 원소를 서로 비교해야한다. 이 것은 2^(n-2)보다 훨씬 큰 효율로
매우, 절대적으로 비효율적인 알고리즘이다.
* 동적프로그래밍 방법
- 경로들을 단계적으로 만들어서 문제를 해결하려고 한다.
- 경로들을 연결 정점들의 집합, L을 이용하여 만들 것이다. 즉, 경로들을 L내에 있는 정점들 만을 이용한다.
예를 들면, 정점 x로부터 정점 y까지 가는 경로는 다음과 같이 L 내에 있는 정점들 만을 표현한다.
- 정확하게 L에 있는 정점들을 추가하는 정해진 순서는 없다.
일반적으로 정점의 번호와 같이 숫자 순서로 추가를 한다.
- 우리는 비용 행렬을 만들어 다음과 같이 차례대로 계산을 할 것이다.
- 위의 형식을 이용하여 계산한 한예는 다음과 같다.
- 위와 같은 과정을 풀기 위해서 우리가 해결해야 할 문제는 D(k) 에서 D(k+1)로 가는 것이다.
- D(k)에서 D(k+1)을 구하는 방법
D(k+1)은 두가지의 문제로 나뉘어 진다.
ⓐ Vk+1 노드를 통과하지 않는 모든 경로의 비용
ⓑ Vk+1 노드를 반드시 통과하는 모든 경로의 비용
> ⓐ의 문제는 D(k)로 되지만 ⓑ의 문제는 또 다시 두가지의 경우로 나뉘어진다.
: ① 시작점에서 k+1노드까지 가능 비용
: ② k+1노드에서 도착점까지 가는 비용
즉, 이전에 있던 배열의 원소를 이용하여 다음의 원소의 답을 구해서 그 자리에 넣을 수 있다.
이를 식으로 나타내면 다음과 같다.
- 알고리즘구현
D = W
for ( k = 1 ; k < n ; k++ ) // 중간에 사용하는 정점을 V1, V2 ,... ,Vn-1로 늘려준다
for ( i = 1 ; i <= n ; i++ ) // 이하는 2개의 정점을 가는 가장 짧은 길을 찾아낸다.
for ( j = 1 ; j <= n ; j++ )
D[i,j] = Min(D[i,j],D[i,k]+D[k,j]);
-------------------------------------------------------------------------------------------
먼가 이해가 잘 안가는 사람은 다음에 나와있는 소스를 참조해주기를 바란다.
- 우리가 흔히 접하는 핸드폰의 지하철 안내도, 자동차의 네비게이션 등은 모두 최단거리 알고리즘을 사용하여서
작동을 한다. 내가 소개하려는 최단 경로도 있지만 요즘은 A*라는 최단 경로 알고리즘이 많이 쓰인다.
- 지금 소개하려는 Floyd알고리즘을 이해하려면, 그래프에 대한 이해가 이미 충분히 되있어야 할 것이다.
* 최단경로를 풀기위해 알아야하는 용어
- 가중치 행렬 W[i][j]
> 정점 i에서 j로 이동하는 화살표가 존재한다면 화살표에 해당하는 가중치
> 정점 i에서 j로 이동하는 화살표가 없다면 무한대
> 정점 i와 j 의 값이 같다며느 0의 값을 가진다.
- 경로비용 : 경로상의 모든 화살표들의 가중치들의 합
- 최단경로 : 경로비용이 가장 작은 경로
- 최단 경로 문제는 최적화(optimization)문제에 속한다.
> 최적화 문제란? 주어진 문제에 대하여 하나 이상의 많은 답이 존재 할때, 이중에서 가장 최적인 답을 찾는 문제
ex)
> v1 ~ v4까지 가는 경로 비용
v1 - v2 - v3 - v4 : 8
v1 - v2 - v4 : 3
v1 - v4 : 1 (최단경로!!)
* 무작정 알고리즘(brute-force Algorithm)
- 한 정점에서 다른 정점으로 가는 모든 경로의 비용을 구한뒤, 그들중의 최소 경로를 찾는다.
- 분석
> 그래프가 n개의 정점을 가지고 있고, 모든 정점들 사이에 화살표가 존재한다고 가정하자. 그러면 한 정점
Vi에서 다른 정점 Vj로 가는 경로들을 다 모아 보면 그 경로들 중에서 나머지 모든 정점을 꼭 거쳐 가는
경로만을 우선적으로 생각해보자.
(ex) 정점이 v1~v5까지 있을때 v2에서 v3으로 가는데 v1,v4, v5를 모두 거차가는 경우)
> n개의 정점이 있을때 Vi에서 출발하여 처음에 도착할 수 있는 정점의 개수는
n-2(n개에서 시작점, 도착점 제외)개 이다. 그 중에 하나를 선택하여 다음에 도착 할 수 있는 정점의 개수는
n-3개이다. 이렇게 계속 반복하다 보면 총 비교해야될 원소의 개수는 (n-2)*(n-3)*...*2*1 = (n-2)!이다.
> 모든 경로가 아닌 특정 경우만해도 (n-2)!개의 원소를 서로 비교해야한다. 이 것은 2^(n-2)보다 훨씬 큰 효율로
매우, 절대적으로 비효율적인 알고리즘이다.
* 동적프로그래밍 방법
- 경로들을 단계적으로 만들어서 문제를 해결하려고 한다.
- 경로들을 연결 정점들의 집합, L을 이용하여 만들 것이다. 즉, 경로들을 L내에 있는 정점들 만을 이용한다.
예를 들면, 정점 x로부터 정점 y까지 가는 경로는 다음과 같이 L 내에 있는 정점들 만을 표현한다.
- 정확하게 L에 있는 정점들을 추가하는 정해진 순서는 없다.
일반적으로 정점의 번호와 같이 숫자 순서로 추가를 한다.
- 우리는 비용 행렬을 만들어 다음과 같이 차례대로 계산을 할 것이다.
- 위의 형식을 이용하여 계산한 한예는 다음과 같다.
- 위와 같은 과정을 풀기 위해서 우리가 해결해야 할 문제는 D(k) 에서 D(k+1)로 가는 것이다.
- D(k)에서 D(k+1)을 구하는 방법
D(k+1)은 두가지의 문제로 나뉘어 진다.
ⓐ Vk+1 노드를 통과하지 않는 모든 경로의 비용
ⓑ Vk+1 노드를 반드시 통과하는 모든 경로의 비용
> ⓐ의 문제는 D(k)로 되지만 ⓑ의 문제는 또 다시 두가지의 경우로 나뉘어진다.
: ① 시작점에서 k+1노드까지 가능 비용
: ② k+1노드에서 도착점까지 가는 비용
즉, 이전에 있던 배열의 원소를 이용하여 다음의 원소의 답을 구해서 그 자리에 넣을 수 있다.
이를 식으로 나타내면 다음과 같다.
- 알고리즘구현
D = W
for ( k = 1 ; k < n ; k++ ) // 중간에 사용하는 정점을 V1, V2 ,... ,Vn-1로 늘려준다
for ( i = 1 ; i <= n ; i++ ) // 이하는 2개의 정점을 가는 가장 짧은 길을 찾아낸다.
for ( j = 1 ; j <= n ; j++ )
D[i,j] = Min(D[i,j],D[i,k]+D[k,j]);
-------------------------------------------------------------------------------------------
먼가 이해가 잘 안가는 사람은 다음에 나와있는 소스를 참조해주기를 바란다.