[인공지능] Uninformed Search - BFS(너비우선탐색)

반갑습니다. :)

 

 

오늘은 Uninformed Search의 첫 번째 기법,

 

BFS(Breadth-first Search)에 대해서 살펴보도록 하겠습니다.

 

 

---

 BFS (Breadth-first Search)
: 너비우선탐색

 

 

BFS는 fringe의 왼쪽부터 오른쪽으로 가며,

밑으로 내려가며 탐색하는 기법입니다.

 

 

 

---

 

Tree형태

 

Goal을 모른다고 가정할 때 A~O까지 탐색하는 과정입니다.

가장 먼저 위에 A가 Goal인지 탐색하고

 

두 번째, 왼쪽에 있는 B가 Goal인지 탐색합니다.

 

다음 오른쪽에 있는 C가 Goal인지 탐색합니다.

 

그 다음 B의 왼쪽인 D가 Goal인지 탐색합니다.

 

D를 탐색 후 오른쪽의 E가 Goal인지 탐색합니다.

 

이와 동일하게 F와

 

G를 차례대로 Goal인지 탐색합니다.

 

마지막 단계에 있는 알파벳도 왼쪽에서 오른쪽으로 차례대로 Goal인지 탐색합니다.

 

 

 

 

 

 

 

 

끝!

 

BFS는 이렇게 탐색을 하는데,

 

 

앞으로 살펴볼

Uninformed Search의 종류에서

각 탐색기법의 성능을 비교할 필요가 있습니다.

성능은 두 가지로

Complete (Goal을 보장하는가?)

Optimal (제일 좋은 Goal을 보장하는가?)

을 비교해야합니다.

 

Complete (Goal을 보장하는가?)
: 정답(Goal)을 보장하는지?

Optimal (제일 좋은 Goal을 보장하는가?)
: 만약 정답(Goal)이 여러개 있을 때, 제일 좋은 정답(Goal)인지?

 

 

BFS의 각 성능은 어떨까요?

 

.

.

.

.

.

.

 

hint!

 

위에서 살펴본

BFS가 탐색하는 그림을 생각해보세요!.!

 

 

 

 

정답은!!

 

Complete (Goal을 보장하는가?) :  O

-> 위에서부터 아래로,

왼쪽에서부터 오른쪽으로,

모든 fringe를 탐색하기 때문에 정답을 무조건 보장합니다.

 

 

 

Optimal (제일 좋은 Goal을 보장하는가?) : O

-> 만약 다음 그림과 같이 정답이 여러개 있다면,

BFS기법을 적용하여 Goal인 C를 먼저 찾고

 

그 다음 D를 탐색 중 Goal을 발견하게 된다면

 

C와 D 중 둘 중

 

먼저 발견한, 가장 빠른 경로인

상단에 있는 C가 더 좋은 Goal이기에

가장 좋은 답을 찾는다는 것을 보장할 수 있습니다.

 

 

 

 

 

하지만,

 

BFS의 가장 큰 단점은

 

Time Complexity입니다.

 

Time Complexity (시간 복잡도)
: 답(Goal)을 찾는데 걸리는 시간

 

 

 

BFS는 모든 fringe를 탐색하기에

 

시간이 엄청 오래 걸립니다.

 

 

Time Complexity (시간 복잡도) : X

-> 모든 fringe을 탐색하기 때문에 시간의 효율성은 좋지 않습니다.

 

 

---

 

 

 

 

오늘은 BFS 기법과

 

그의 성능에 대해서 살펴보았습니다.

 

 

 

<BFS 성능>

Complete (Goal을 보장하는가?)	Optimal (제일 좋은 Goal을 보장하는가?)	Time Complexity (시간 복잡도)
O	O	X

 

 

 

 

 

다음에 게시될 기법에서도

 

성능을 비교하면서 살펴보도록 하겠습니다!

 

.

.

.

 

 

BFS List형태 및 DFS와 비교

https://setori-dev.tistory.com/46

[인공지능] Uninformed Search - BFS와 DFS 비교

 

 

 

 

많은 도움 되셨다면❤와 구독 부탁드릴게요!

 

:)