[인공지능] 깊이 우선 탐색 ( DFS; Deep First Search )

 

알파고는 딥러닝으로 가장 가능성 높은 몇 개의 수를 추려낸 후 탐색기법을 적용하여 다음 수를 읽었다. 361! 개의 경우의 수에서 가능성 있는 1000가지를 추리고 1000가지에 탐색기법을 적용한다. 이번 포스팅에서는 탐색기법을 다루어 보겠다. 

 

 

 

 

탐색(Search)이란,

 

상태공간에서 초기상태에서 목표상태까지의 경로를 찾는 것이 탐색이다. 

연산자는 다음 상태를 생성한다. 

 

 

 

 

맹목적 탐색 ( 목적없이 탐색 )

 

- 깊이 우선 탐색

- 너비 우선 탐색

- 균일 비용 탐색

 

깊이 우선 탐색 ( DFS; Deep First Search )

 

해가 존재할 가능성이 있는 한 앞으로 계속 전진하여 탐색하는 방법

탐색 대상인 '노드(Node)'는 동적으로 생성된다. ( 미리 생성 X )

 

 

OPEN-CLOSED 리스트

 

확장이 가능한 상태(노드)는 동적으로 생성된다. 동적으로 생성된 노드 중 이미 탐색했던 상태와 동일한 상태가 존재할 수 있다. 동일한 상태를 검사하는 오버헤드를 줄이기 위해 두 가지 리스트를 사용한다. 

 

- OPEN 리스트 : 확장은 되었으나 탐색되지 않은 상태 리스트

- CLOSED 리스트 : 탐색이 끝난 상태 리스트

 

 

DFS 알고리즘

 

1. OPEN 리스트에 시작 노드를 넣는다. 리스트는 Stack 자료구조이다. 

 

2. 탐색과정은 OPEN 리스트가 모두 비어지(Empty)거나 목표상태를 찾을 때까지 반복(while)된다.

 

3. OPEN 리스트(스택)를 POP하여 상태(노드)를 가져온다.  목표상태가 아니라면 자식 노드를 생성한다. 

 

 

4. A는 CLOSED 리스트(스택)에 추가(PUSH)한다. B 와 C는 OPEN 리스트와 CLOSED 리스트에 중복되는 상태가 있는지 검사한 뒤 없다면 OPEN 리스트에 추가(PUSH)한다. 

 

5. OPEN 리스트가 비어지거나 목표상태를 찾을 때까지 위 과정을 반복한다.