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

반갑습니다. :)

 

 

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

 

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

 

 

---

DFS (Depth-first Search)
: 깊이우선탐색

 

 

DFS는 가장 왼쪽 깊게 있는 fringe를 탐색하는 기법입니다.

 

 

 

---

 

Tree형태

 

 

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

 

 

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

 

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

 

그 다음 B의 가장 왼쪽인 D가 Goal인지 탐색하고,

 

D의 가장 왼쪽인 H를 Goal인지 탐색하고,

 

가장 깊게 있는 왼쪽 H를 탐색했으니, 그 다음 I가 Goal인지 탐색합니다.

 

다음, B의 가장 왼쪽인 D의 탐색이 끝났기 때문에 E가 Goal인지 탐색합니다.

 

E의 왼쪽인 J와

 

K가 Goal인지 탐색하면 B의 전체 탐색이 끝났습니다.

 

가장 왼쪽에 있었던 B의 탐색이 끝났으면, 오른쪽에 있던 C도 동일하게 진행합니다.

 

 

 

 

 

끝!

 

 

 

 

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

 

 

앞서 BFS와 같이

 

앞으로 살펴볼

Uninformed Search의 종류에서

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

 

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

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

 

 

 

 

성능은 두 가지로

Complete (Goal을 보장하는가?)

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

을 비교해야합니다.

 

 

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

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

 

 

 

DFS의 각 성능은 어떨까요?

 

.

.

.

.

.

.

 

hint!

 

위에서 살펴본

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

 

 

 

 

정답은!!

 

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

-> 하지만! 끝이 있다는 유한(limit, 제한)한 깊이에서,

가장 깊은 왼쪽에서부터 오른쪽까지

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

 

 

 

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

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

DFS기법을 적용하여 Goal인 I를 먼저 찾고

 

 

 

 

B의 탐색을 모두 마친 후에

Goal인 C을 발견하게 된다면

 

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

상단에 있는 C가 더 좋은 Goal을 무시하고

I를 먼저 찾아 Goal로 발견이 되었기 때문에

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

 

 

 

 

 

 

덧붙여 DFS는

 

BFS의 가장 큰 단점인

 

Time Complexity은 비교적으로 해결할 수 있습니다.

 

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

 

 

 

하지만 DFS는 BFS와 동일하게

 

모든 fringe를 탐색하기에

 

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

 

 

시간 복잡도를 계산해보면

 

큰 차이는 없지만 BFS보다는 빨리 찾습니다.

 

 

 

Time Complexity (시간 복잡도) : △

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

 

 

 

---

 

 

 

 

오늘은 DFS 기법과

 

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

 

 

 

<DFS 성능>

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

 

 

 

 

 

다음에 게시될 기법에서도

 

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

 

 

.

.

.

 

 

DFS List형태 및 BFS와 비교

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

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

 

 

 

 

 

 

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

 

:)