Basic Search Method: Bidirectional Search

기본 검색 방식: 양쪽에서 찾는 검색방식

Basic Search Method: Bidirectional Search

검색방식 설명	그림	코드와 예제	검색 비교	자료

양쪽에서 부터 찾는 방식에 대한 설명
Bidirection search, 즉, 두개의 방항에서 검색하는 방식은 처음인 시작과 마지막 인 목표 에서 부터 한단계식 움직여서 같이 만나는 장소에서 멈추는 검색 방식입니다. 이 검색은 시작과 목표를 아는 상태에서 검색을 시작 하는 것입니다. 이 검색방식은 검색하는 가지수(braching factor)를 줄임으로써 시간과 공간을 Breadth-First 에 비해 많이 줄일수 있습니다. 예를 들면 가지수(branching factor)가 10이고 깊이(depth) 가 6인 Breadth-First를 검색할려면 총 1,111,111 를 검색해야 됩니다. Breadth-First는 b^d라는 형식으로 10⁰ + 10¹ + 10² + 10³ + 10⁴ + 10⁵ + 10⁶ = 1,111,111 의 가지수가 있습니다. 그러나 Bidirection 검색을 이용하면 아까의 Breadth-First로한 검색을 깊이의 반을 2개로 나누기 때문에 총 2,222 가지를 검색합니다. 2b^d/2 이므로 10⁰ + 10¹ + 10² + 10³ = 1,111 * 2(양쪽에서) = 2,222. 이 검색 방식을 사용할려면 다음과 같은 점을 고려 해야 합니다. 뒤에서 부터 검색한다는 것을 어떻게 응용할것인가를 생각해야 합니다. 하나의 가지수는 일정합니다. 예를 들어 가지가 10개씩 분리가 되면, 10개씩 분리가 되면서 그 아래의 것도 10개씩 나누어 집니다. 그것을 뒤에서 부터 검색하는것에 대한 생각이 있어야 할것 입니다. 뒤에서 시작할때의 전자가 앞에서 시작할때는 후자로 바꾸어주는 것이 주로 힘듭니다. 위에서 아래로 내려가는 것을 반대로 하면서 상태가 달라지지 않게 하기 위한 생각이지요. 그리고 또 바꾸어 줄수 있다는 것도 어려울수 있습니다. 만약에 목적이 여러가지가 있다면 어떻게 여러가지 목적을 달성하는 해답을 찾을때 여러가지 목적에 맞게 여러가지 해답을 찾을수 있도록 해야 할것 입니다. 새로 생기는 가지를 두곳에 넣지 않도록 하는것도 고려해야 될 문제 입니다. 새로운 자료를 넣을때 2장소 (시작과 목표) 에 잘 선택 하셔서 한곳에 넣는것 입니다. 어떠한 검색 방법이 쓰여지는 것도 잘 고려해 보아야 할 문제 입니다. Breadth-First 를 사용할 것인가 Uniform-Cost를 사용하면 더 좋은가 하고, 여러가지 검색 방법을 비교한뒤에 여기에 맞게 사용을 해야 할것 입니다. Bidirectional search는 검색 시간을 상상을 초월할 정도로 줄일수 있습니다. 그러나 항상 사용될수 있는것이 아닙니다.

양쪽에서 부터 찾는 방식에 대한 설명

Bidirection search, 즉, 두개의 방항에서 검색하는 방식은 처음인 시작과 마지막 인 목표 에서 부터 한단계식 움직여서 같이 만나는 장소에서 멈추는 검색 방식입니다. 이 검색은 시작과 목표를 아는 상태에서 검색을 시작 하는 것입니다. 이 검색방식은 검색하는 가지수(braching factor)를 줄임으로써 시간과 공간을 Breadth-First 에 비해 많이 줄일수 있습니다. 예를 들면 가지수(branching factor)가 10이고 깊이(depth) 가 6인 Breadth-First를 검색할려면 총 1,111,111 를 검색해야 됩니다. Breadth-First는 b^d라는 형식으로 10⁰ + 10¹ + 10² + 10³ + 10⁴ + 10⁵ + 10⁶ = 1,111,111 의 가지수가 있습니다. 그러나 Bidirection 검색을 이용하면 아까의 Breadth-First로한 검색을 깊이의 반을 2개로 나누기 때문에 총 2,222 가지를 검색합니다. 2b^d/2 이므로 10⁰ + 10¹ + 10² + 10³ = 1,111 * 2(양쪽에서) = 2,222.

이 검색 방식을 사용할려면 다음과 같은 점을 고려 해야 합니다.

뒤에서 부터 검색한다는 것을 어떻게 응용할것인가를 생각해야 합니다. 하나의 가지수는 일정합니다. 예를 들어 가지가 10개씩 분리가 되면, 10개씩 분리가 되면서 그 아래의 것도 10개씩 나누어 집니다. 그것을 뒤에서 부터 검색하는것에 대한 생각이 있어야 할것 입니다.
뒤에서 시작할때의 전자가 앞에서 시작할때는 후자로 바꾸어주는 것이 주로 힘듭니다. 위에서 아래로 내려가는 것을 반대로 하면서 상태가 달라지지 않게 하기 위한 생각이지요. 그리고 또 바꾸어 줄수 있다는 것도 어려울수 있습니다.
만약에 목적이 여러가지가 있다면 어떻게 여러가지 목적을 달성하는 해답을 찾을때 여러가지 목적에 맞게 여러가지 해답을 찾을수 있도록 해야 할것 입니다.
새로 생기는 가지를 두곳에 넣지 않도록 하는것도 고려해야 될 문제 입니다. 새로운 자료를 넣을때 2장소 (시작과 목표) 에 잘 선택 하셔서 한곳에 넣는것 입니다.
어떠한 검색 방법이 쓰여지는 것도 잘 고려해 보아야 할 문제 입니다. Breadth-First 를 사용할 것인가 Uniform-Cost를 사용하면 더 좋은가 하고, 여러가지 검색 방법을 비교한뒤에 여기에 맞게 사용을 해야 할것 입니다.

Bidirectional search는 검색 시간을 상상을 초월할 정도로 줄일수 있습니다. 그러나 항상 사용될수 있는것이 아닙니다.

그림의 예제

이 그림은 Breadth-First방식의 검색으로 퍼져가고 있습니다. 시작(Start)과 목적(Goal)이 있지요. 시작과 목적이 이어지면 성공한 것입니다. 지금 그림은 이어질것 같은 상태를 보여줌으로써 성공가까이에 있습니다.

사용할수 있는 예를 들어보겠습니다. 시작(Star State)에서 목적(Goal State) 로 가는 방식을 찾을수 있는 검색으로 사용되어서 쓰여질수 있습니다. 목적 을 달성하기 위해서는 여러가지 방법이 있는데, 여기에 쓰이는 다른 검색 방식들 Heuristic Functions 도 고려하는 것도 필요할 것 입니다.

여기에 대한 예제는 없습니다. 죄송합니다.

다른 검색 방법들과 비교
Criterion	Breadth-First	Uniform-Cost	Depth First	Depth-Limited	Iterative Deepening	Bidirectional (if applicable)
Time(시간) Space(공간) Optimal?(최상적인 답) Complete?(완벽하게 다 검색)	b^d b^d YES YES	b^d b^d YES YES	b^m bm NO NO	b^l bl NO YES, if l ≥ d	b^d bd YES YES	b^d/2 b^d/2 YES YES
여기서의 b는 나누어지는 가지 수. (branching factor) d 는 깊이 입니다. (depth) m 는 최대 깊이입니다. (maximum depth) l 은 깊이의 한계입니다. (depth limit)

이 자료는 Artificial Intelligence, A Modern Approach에서 공부한 내용중의 하나를 한글로 쓴것입니다. 참고로 figure 3.17 그림은 책 81쪽에서 복사한 내용입니다. figure 4.7 그림은 책 101에서 복사한 내용입니다.

여기에 대한 질문이 있으시면 kee@unforgettable.com 으로 메일주시면 답변드리겠습니다.