[인공지능] 넓이 우선 탐색 ( BFS; Breadth First Search )

 

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

 

- 깊이 우선 탐색

- 너비 우선 탐색

- 균일 비용 탐색

 

 

넓이 우선 탐색 ( BFS; Breadth First Search )

 

루트 노드의 모든 자식 노드를 탐색한 다음 해가 없으면 다음 레벨로 넘어가 탐색하는 알고리즘

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

 

 

 

 

OPEN-CLOSED 리스트

 

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

 

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

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

 

 

 

BFS 알고리즘

 

1. OPEN 리스트에 시작노드를 넣는다. DFS는 리스트로 Stack 자료구조를 사용한다. BFS는 리스트로 Queue 자료구조를 사용한다. 

 

 

 

 

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

 

 

3. OPEN 리스트에서 선입선출(FIFO)하여 노드를 가져온다. 노드가 목표 노드가 아니라면 자식노드를 생성한다.(확장)

 

 

4. 부모 노드(A)는 CLOSED 리스트에 넣는다. 자식 노드(B,C)는 OPEN 리스트와 CLOSED 리스트에서 중복검사를 한 후, 중복되지 않으면 OPEN 리스트에 넣는다. 

 

 

 

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