Graph

Solve the exercise problem 14 of the chapter 7

합병 정렬은 크게 분할, 정복, 합병으로 구성되어 있다. 이때 레코드 저장 횟수를 계산하기 위해서는 각 과정에서 레코드가 저장되는 횟수를 살펴보아야 한다.

 

1. 분할 과정

입력 배열을 반으로 나누는 과정에서는 레코드 저장이 필요하지 않기에 레코드 저장 횟수는 0이다.

 

2. 정복 과정

각각 작은 배열을 정렬하는 과정에서 레코드를 저장한다. 이때, 레코드 저장 횟수는 배열의 크기에 비례하기 때문에 작은 배열의 크기가 k인 경우 레코드 저장 횟수는 2klogk(양쪽 배열의 레코드 저장 횟수)이다.

 

3. 합병 과정

정렬된 작은 배열을 합병하여 더 큰 배열을 만들 때 레코드 저장이 필요하다. 두 배열의 요소를 비교하면서 더 작은 값을 새로운 배열에 저장하는데, 이때 새로운 배열에 레코드를 저장하는 횟수가 발생한다. 여기서 레코드 저장 횟수는 두 배열의 크기에 비례한다. 따라서 레코드 저장 횟수는 2klogk이다.

 

T(n) = 2*T(n/2) + O(n)

T(n) = 2cnlogn

2cnlogn = 2*2c(n/2)(logn - 1) + O(n)

O(n) = 2cn

 

The source vertex is 's', and the target vertex is 'D'에 대해 양방향 탐색 그리기

그림1

위 그림의 경우, 빨간색 선과 파란색 선의 부분만 고려하면 양방향 탐색으로 최단 경로를 구할 수 있다. 따라서, 빨간색 선의 u + u' 값과 파란색 선의 u' + u의 가중치 값만을 고려해 최단 경로를 찾을 수 있다.

 

아래 예시를 살펴보자.

S와 D에서 동시에 출발한다면 두 탐색이 노드 B, 노드 C에서 만나게 되고 최단 경로는 바로 11이 된다. 하지만, 이 경로는 최단 경로가 아니다. 아래서 최단 경로를 어떻게 찾을 수 있는지 살펴보고자 한다.

Can you improve this Bi-Directional Search algorithm?

그림2

 

그림1의 가중치를 약간만 바꿨을 때, 빨간색 선과 파란색 선 부분만 고려해서 양방향 탐색을 진행할 경우 오히려 최단 경로를 찾지 못하게 된다. u + u'의 가중치만 고려했을 때, 당장 u + u' 값이 w보다 큰 값을 갖기 때문에 실제 최단 경로인 s - u - u' - t, t - u' - u - s가 아닌 다른 경로를 최단 경로로 삼게 된다. 따라서, 이 문제를 해결하기 위해 u, u'뿐만 아니라 그 다음 노드의 가중치까지도 고려해야 한다.

 

실제 예시에 적용해보자.

처음 양방향 탐색을 하고 멈췄을 때는 최단 경로가 11로 나왔다. 하지만 두 탐색이 만나고나서 한 번 더 다음 노드의 가중치를 고려해 가중치의 변화가 없다면 최단 경로가 된다.