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

반갑습니다. :)

 

 

Uninformed Search의

 

BFS와 DFS 탐색을

 

List로

 

비교해보도록 하겠습니다.

 

 

---

BFS (너비우선 탐색)

: 밑으로 내려가면서 탐색

 

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

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

 

 

---

 

List형태

 

다음을 BFS기법으로 탐색하는 과정을 List로 표현하시오.

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

 

 

맨 처음 a가 Open List에 들어오고

Open	a
Close

 

 

Open List에 들어온

 

a를 탐색하고, 확장하고자 할 때

 

a가 Close List로 들어옵니다.

 

Open	a
Close	a 확장

 

 

즉,

 

a가 Close List에 들어오면

 

a의 fringe를 확장할 수 있습니다.

 

 

확장한 a의 fringe은 b와 c로

 

Open List로 들어옵니다.

Open	a	b	c
Close	a 확장

 

 

그 다음

 

BFS이기 때문에 b를 먼저

 

앞의 a와 동일하게 fringe를 확장합니다.

 

 

b의 fringe은 d와 e로

 

다음 Open List로 들어옵니다.

Open	a	b	c	d	e
Close	a 확장	b 확장

 

 

다음 List의 순서대로

 

c를 확장합니다.

 

(c의 fringe는 f와 g인 것 이해 되시죠?)

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장

 

 

그럼 모든 fringe가 Open List에 들어왔고,

 

Open List 순서대로 확장을 합니다.

 

d~g는 아래의 fringe가 없기 때문에 순서대로 Close List에 들어오게됩니다.

 

 

d 확장

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장	d 확장

 

 

e 확장

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장	d 확장	e 확장

 

 

f 확장

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장	d 확장	e 확장	f 확장

 

 

g 확장

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장	d 확장	e 확장	f 확장	g 확장

 

 

 

이렇게 탐색의 순서는 Close List에 들어온 순서대로 진행됩니다.

 

따라서, 탐색 순서는 다음과 같습니다.

a , b , c , d , e , f , g

 

 

 

 

---

 

 

 

앞서 BFS의 탐색과

 

DFS의 탐색을 비교해보도록 하겠습니다.

 

 

DFS (깊이우선 탐색)

: 왼쪽부터 깊게 탐색

 

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

[인공지능] Uninformed Search - DFS(깊이우선탐색)

 

 

---

 

List형태

 

 

다음을 DFS기법으로 탐색하는 과정을 List로 표현하시오.

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

 

 

동일하게

 

맨 처음 a가 Open List에 들어오고

Open	a
Close

 

 

Open List에 들어온

 

a를 탐색하고, 확장하고자 할 때

 

a가 Close List로 들어옵니다.

Open	a
Close	a 확장

 

 

즉,

 

a가 Close List에 들어오면,

 

a의 fringe를 확장할 수 있습니다.

 

확장한 a의 fringe은 b와 c로

 

Open List로 들어옵니다.

Open	a	b	c
Close	a 확장

 

 

그 다음

 

DFS이기 때문에 b를 먼저

 

앞의 a와 동일하게 b의 fringe를 확장합니다.

 

 

b의 fringe은 d와 e로

 

다음 List로 들어옵니다.

Open	a	b	d	e	c
Close	a 확장	b 확장

(즉, c를 탐색하기 전에 d와 e를 탐색해야하므로,

 

c의 앞으로 배치가 됩니다.)

 

여기서 BFS의 차이점을 아시겠나요?

 

 

 

다음 List의 순서대로

 

d를 확장합니다.

Open	a	b	d	e	c
Close	a 확장	b 확장	d 확장

 

 

그렇다면!!

 

현재 진행사항은 다음과 같습니다.

왼쪽만 탐색한 상태

 

 

 

이제 순서대로

 

e 확장

Open	a	b	d	e	c
Close	a 확장	b 확장	d 확장	e 확장

 

c를 확장하면

 

f와 g가 Open List에 들어오면서

 

모든 fringe가 List에 들어오게 됩니다.

Open	a	b	d	e	c	f	g
Close	a 확장	b 확장	d 확장	e 확장	c 확장

 

 

마지막으로

 

f 확장

Open	a	b	d	e	c	f	g
Close	a 확장	b 확장	d 확장	e 확장	c 확장	f 확장

 

 

g 확장

Open	a	b	d	e	c	f	g
Close	a 확장	b 확장	d 확장	e 확장	c 확장	f 확장	g 확장

 

이렇게 탐색의 순서는 Close List에 들어온 순서대로 진행됩니다.

 

따라서, 탐색 순서는 다음과 같습니다.

a , b , d , e , c , f , g

 

 

 

 

 

---

 

 

 

 

이렇게 BFS와 DFS의 탐색을

 

비교하면 다음과 같습니다.

 

 

 

BFS 탐색

a , b , c , d , e , f , g

 

 

DFS 탐색

a , b , d , e , c , f , g

 

 

 

List로 보게 되면,

 

 

BFS 탐색

-> 일렬로 들어오는 순서대로 차례대로 진행

Queue(큐)형

Open	a	b	c	d	e	f	g
Close	a 확장	b 확장	c 확장	d 확장	e 확장	f 확장	g 확장

 

DFS 탐색

-> 쌓는형태로 가장 마지막에 들어온 것부터 진행

Stack(스택)형

Open	a	b	d	e	c	f	g
Close	a 확장	b 확장	d 확장	e 확장	c 확장	f 확장	g 확장

 

 

 

 

두 기법의 차이점을 이해가 되셨나요?

 

 

 

 

 

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

 

:)