[인공지능] Uninformed Search - UCS(균일비용탐색)

반갑습니다. :)

 

 

오늘은 Uninformed Search의 마지막 기법,

 

UCS(Uninform-cost Search)에 대해서 살펴보도록 하겠습니다.

 

 

---

 UCS (Uninform-cost Search)
: 균일비용탐색

 

 

UCS는 fringe마다 비용을 적어

 

가장 적은 비용으로 탐색하는 기법입니다.

 

 

 

이때, 탐색은

 

BFS를 기반으로 진행되며,

 

적은 비용에 따라 확장합니다.

 

 

 

 

 

---

 

Tree형태

 

 

 

그림. Goal을 모른다고 가정할 때 a~g까지의 탐색 경로입니다.

 

 

 

이를 연결하는 선을

 

Tree로 표현하면 다음과 같습니다.

 

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

 

 

먼저 a가 Goal인지 탐색합니다. a가 시작이기 때문에 비용은 0입니다.

 

이 때, a의 fringe를 확장하면 b와 c인데, 여기서 비용이 작은 fringe를 선택합니다. (비용은 그림에 적힌 값입니다.)

 

b의 비용:  5

c의 비용: 4

 

때문에 적은 비용인 c가 Goal인지 탐색합니다.

 

 

 

c가 Goal인지 탐색하면서, 확장합니다.

 

 

이때, 비용은

 

그림에서의 거리별 비용을 더한 값입니다.

 

 

b의 비용:

a->c->b 거리

0+4+5=9

 

d의 비용:

a->c->d 거리

0+4+3=7

 

e의 비용:

a->c->e 거리

0+4+8=12

 

 

 

여기서,

 

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

 

이때, b가 두 가지로 중복이 되는데, 적은 비용으로 선택하여

 

큰 비용의 b(9)의 탐색은 중지합니다.

 

그 후

 

b, d, e 중 가장 적은 비용을 선택하여

 

확장합니다.

 

 

 

b 확장

 

 

 

여기서,

 

다시한번 비용을 비교합니다.

 

 

동일하게 같은 fringe일 경우, 적은 비용의 fringe를 선택합니다.

 

 

c는 4가 작은 비용으로 확장했으니 c10 삭제, d12은 적은 비용 d7가 존재하기 때문에 삭제, e12는 적은비용 e11가 존재하기 때문에 삭제

 

삭제가 되었으면,

 

남은 fringe에서 비용을 비교합니다.

 

 

 

가장 적용 비용인 d가 7이기 때문에

 

d를 확장합니다.

 

d 확장

 

 

 

동일하게 비용을 비교합니다.

 

같은 fringe인 b의 큰 비용을 삭제하고, f가 가장 적은 비용을 가지고 있습니다. 그렇기에 다음은 f를 확장합니다.

 

 

 

한번 더 동일하게 비용을 비교합니다.

 

e와 g를 비교하면, e가 적은 비용이기 때문에 끝내지 않고 확장을 합니다.

 

 

마지막으로 비용을 비교합니다.

 

 

여기서 동일한 fringe인 g14를 삭제하고, 가장 적은 비용의 fringe를 선택합니다.

 

 

마지막으로 g를 확장하게 된다면, 확장할 값이 없기 때문에 g가 Goal임을 알 수 있습니다.

 

 

 

즉,

 

a->b->e->g로

 

가는 경로도 있지만

 

비용은 14이고,

 

 

a->c->d->f->g의

 

비용이 12이기 때문에

 

 

두 번째 경로가

 

더 적은 비용으로 탐색을 할 수 있습니다.

 

 

 

 

 

 

 

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

 

앞서 BFS, DFS와 같이

 

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

 

 

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

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

 

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

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

 

 

 

 

 

성능은 두 가지로

Complete (Goal을 보장하는가?)

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

을 비교해야합니다.

 

 

 

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

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

 

 

 

UCS의 각 성능은 어떨까요?

 

.

.

.

.

.

.

 

hint!

 

위에서 살펴본

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

 

 

 

 

 

정답은!!

 

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

-> BFS를 기반으로 진행되기 때문에

위에서부터 아래로,

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

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

 

 

 

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

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

BFS는 비용을 비교하지 않기 때문에 D가 최적의 정답이지만

 

비용으로 비교했을 때는 G가 6, D가 8이기 때문에 G가 최적의 정답이다.

 

 

즉, 적은비용만으로 정답을 찾기 때문에

 

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

 

 

 

 

 

덧붙여 UCS의

 

Time Complexity은 비교적으로 복잡하지만, 빠릅니다.

 

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

 

 

 

하지만 비용을 측정하고, 비교하기 때문에

 

공간(메모리)가 많이 차지하는 것을 볼 수 있습니다.

 

 

 

Time Complexity (시간 복잡도) : △

-> 비용을 비교하여 정답을 찾기 때문에 시간의 효율성은 비교적 좋습니다.

 

 

 

---

 

 

 

 

오늘은 UCS 기법과

 

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

 

 

 

<UCS 성능>

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

 

 

 

 

 

이렇게 Uninformed Search의

 

대표적인 기법에 대해서 살펴보았습니다.

 

 

 

다음은 informed Search에 대해서

 

살펴보도록하겠습니다!

 

 

.

.

.

 

 

UCS List형태로 보기

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

[인공지능] Uninformed Search - UCS List로 분석

 

 

 

 

 

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

 

:)