[Algorithms] 탐색(Search)

너비 우선 탐색(Breadth-first Search)에서는 모든 경우를 망라해서 탐색 트리 전체를 작성해간다. 이런 의미에서 너비 우선 탐색에서는 탐색 대상이 되는 상태 공간 전체를 탐색할 수 있다. 하지만 탐색할 수 있다는 것일 뿐 목표 노드의 발견을 보장하지는 않는다. 애초에 목표 노드가 없다면 당연히 답을 찾을 수 없다. 또한, 단순한 너비 우선 탐색에서는 조합적 확산을 통해 금방 노드 수가 메모리에 들어가지 않을 만틈 늘어나버린다. 그럼에도 너비 우선 탐색은 탐색 기술의 기본이 되는 방법이다.

 

※ 조합적 확산

조합에 따라 상태 수가 방대해지는 현상

 

너비 우선 탐색 알고리즘

1. 오픈 리스트와 클로즈드 리스트 초기화

2. 오픈 리스트 끝에 루트 노드 삽입

아래 과정 반복

3. 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못한 경우)

4. 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견한 경우)

5. 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개

6. 전개된 노드 중 오픈 리스트 또는 클로즈드 리스트의 노드와 중복되지 않는 노드를 오픈 리스트의 끝에 추가

7. 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

 

너비 우선 탐색과는 달리 깊이 우선 탐색(Depth-first Search)에서는 어떤 노드를 얻으면, 곧바로 해당 노드를 전개한다. 깊이 우선 탐색은 너비 우선 탐색과 마찬가지로 탐색 트리 전체를 생성할 수 있는 알고리즘이다. 하지만 이 방법 역시 너비 우선 탐색처럼 유한한 시간 내에 모두 탐색할 수 있는 것은 아니다. 예를 들어, 무한한 깊이의 경로가 있다면 깊이 우선 탐색에서는 그 경로를 계속해서 탐색해가기 때문에 탐색이 끝나지 않는 경우가 있다. 

 

깊이 우선 탐색 알고리즘

1. 오픈 리스트와 클로즈드 리스트 초기화

2. 오픈 리스트 맨 앞(맨 뒤)에 루트 노드 삽입

아래 과정을 반복

3. 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못한 경우)

4. 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견한 경우)

5. 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개

6. 전개된 노드 중 클로즈드 리스트의 노드와 중복되지 않는 노드를 오픈 리스트 맨 앞에 추가하고, 만약 오픈 리스트에 중복이 있다면 오픈 리스트에서 해당 노드 삭제

7. 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

 

너비 우선 탐색과 깊이 우선 탐색은 미리 정한 순서에 따라 망라하여 탐색하는 기법이다. 이런 탐색 기법은 문제에 의존하지 않는 범용적인 방법이지만 탐색 효율은 좋지 않다. 다시 말하면, 탐색에 성공하더라도 그 경로가 최단 경로라는 보장이 없다.

 

최상 우선 탐색(Best-first Search)은 탐색의 방향성을 부여하여 '좋아 보이는' 방향부터 탐색을 진행한다. 최상 우선 탐색은 문제의 특성을 이용함으로써 탐색 효율을 높이는 지적인 탐색 기법이다. 최상 우선 탐색에서 탐색의 단서가 되는 값을 반환하는 휴리스틱(Heuristic) 함수가 사용된다. 휴리스틱은 발견, 경험적이라는 의미의 단어이고, 휴리스틱 함수는 경험적으로 탐색을 수행하는 수단으로 이용하는 함수이다. 탐색 문제에서는 탐색 순서에 관한 정답을 사전에 알 수 없으므로, 정답 대신 차선책으로 휴리스틱 함수를 이용한 평가 값을 이용해 탐색 순서를 제어한다. 다만, 휴리스틱 함수는 경험적인 단서이므로 반드시 올바른 탐색 순서를 제공한다고 단정할 수 없다. 최상 우선 탐색 알고리즘은 너비 우선 탐색 알고리즘에 휴리스틱을 이용한 탐색 순서 제어를 더한 형식이 된다. 

 

최상 우선 탐색 알고리즘

1. 오픈 리스트와 클로즈드 리스트 초기화

2. 오픈 리스트 끝에 루트 노드 삽입

아래 과정 반복

3. 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못한 경우)

4. 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견한 경우)

5. 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개

6. 전개된 노드 중 오픈 리스트 또는 클로즈드 리스트의 노드와 중복되지 않는 노드를 오픈 리스트의 끝에 추가

7. 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

8. 오픈 리스트를 평가해 순서를 재정렬

 

최상 우선 탐색에서는 오픈 리스트와 클로즈드 리스트를 이용해 탐색 순서를 제어한다. 가령 휴리스틱 함수가 바람직하지 않은 값을 반환했다고 뒤로 되돌아가 탐색을 진행할 수 있다. 반면, 다음에 전개해야 할 노드로 휴리스틱 함수를 이용해 결정한 최상의 노드만을 이용하고, 그 외의 노드를 전개하지 않는 방법도 생각해볼 수 있다. 이 탐색 방법을 등산법(Hill Climbing)이라고 부른다. 등산법에서는 오픈 리스트와 클로즈드 리스트가 필요 없으므로 탐색 알고리즘이 매우 단순해진다. 하지만 휴리스틱 함수의 반환 값이 부적절하여 잘못된 방향으로 탐색이 진행되면 되돌아갈 수 없기 때문에 정답이 나오지 않으면 의미가 없는 탐색 문제에는 적절한 방법이 아니고, 수치 해석 분야에서 함수의 극한값을 구하는 문제 등에 적합하다.

 

최상 우선 탐색 알고리즘은 탐색 처리의 효율화를 의도한 알고리즘이다. 최상 우선 탐색에서 휴리스틱 함수가 적절하게 설정되어 있으면 탐색에 필요한 계산량을 크게 절약할 가능성이 있지만, 구해진 결과가 최적이라는 보장은 없다. 이러한 문제를 해결하는 최적 경로 탐색에서는 탐색 과정에서 얻은 노드의 시작 노드로부터의 평가 값의 적산치 v를 이용해서 최적 경로를 탐색한다. 

 

최적 경로 탐색 알고리즘

1. 오픈 리스트와 클로즈드 리스트 초기화

2. 오픈 리스트 끝에 루트 노드 삽입

아래 과정 반복

3. 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못한 경우)

4. 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견한 경우)

5. 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개

6. 전개된 노드 중 오픈 리스트의 노드와 중복이 있을 때는 평가가 좋은 쪽을 남기고 클로즈드 리스트의 노드와 중복되지 않는 노드를 오픈 리스트 끝에 추가함

7. 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

8. 오픈 리스트를 평가가 좋은 순서로 재정렬

 

A 알고리즘은 탐색 경로의 적산치 v와 다음 탐색 노드에 대한 추정 값 h를 모두 이용하는 탐색 알고리즘이다. A 알고리즘에서는 최상 우선 탐색의 휴리스틱 함수 h 값과 최적 경로 탐색의 적산치 v로부터 구해지는 값을 평가 값 f로 이용한다. 일반적으로 A 알고리즘이 꼭 최적 경로를 탐색할 수 있는 것은 아니고, 휴리스틱 함수 h의 값이 항상 찾고자하는 목표 함수 g의 값보다 작을 때 최적 경로를 찾을 수 있다. h가 g보다 항상 작다는 조건이 만족된 경우를 A* 알고리즘이라 한다.

 

A 알고리즘

1. 오픈 리스트와 클로즈드 리스트 초기화

2. 오픈 리스트 끝에 루트 노드 삽입

아래 과정 반복

3. 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못한 경우)

4. 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견한 경우)

5. 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개

6. 전개된 노드 중 오픈 리스트의 노드와 중복이 있을 때는 평가가 좋은 쪽을 남기고 클로즈드 리스트와 중복이 있을 때 전개된 노드 쪽이 평가가 좋으면 클로즈드 리스트에서 대응하는 노드를 삭제한 후 오픈 리스트 끝에 노드를 추가함

7. 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

8. 오픈 리스트를 평가가 좋은 순서로 재정렬