[인공지능] Informed Search - Best First Search

 

반갑습니다 :>

 

 

 

 

 

오늘은 Imformed Search의 첫 번째 기법인

 

Best-First Search에 대해서

 

살펴보도록 하겠습니다.

 

 

 

---

 

Best-First Search

 

그림에서 보면 g(n)은 활용하지 않고 h(n)만 활용!

 

 

Best-First Search은

 

 

트리 내 Evaluation function(평가 함수)인

 

f(n)에 의해서

 

 

비용이 가장 적은노드를 예측하여

 

가장 먼저 탐색하는 기법입니다.

 

 

 

 

여기서

 

"비용이 가장 적은"이라는 뜻은

 

Heuristic function(휴리스틱 함수)인

 

h(n)입니다.

 

 

 

즉, h(n)은

 

Goal로 갈 수 있는

 

최소 비용을 예측하는 추정값을 가지고 있습니다.

 

 

 

---

 

하나의 예시로 tic-tac-toe 게임을

 

보도록 하겠습니다.

 

출처: https://run.edu.ng/directory/oermedia/17249353595542.pdf

 

 

이 게임을 이길 수 있는 전략은 무엇일까요?

 

 

 

그 전에

 

tic-tac-toe 게임의 나올 수 있는 경우의 수는

 

9! = 약 36만가지

 

 

입니다.

 

 

 

전 글에서 살펴본

 

Uninforemd Search로 해결하려면

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

[인공지능] Uninformed Search

 

 

36만가지의 모든 경우의 수를

 

하나씩 다 탐색해야합니다.

 

...(•̥̥̥⌓•̥̥̥)

 

 

 

 

이를 더 빠르고

 

정확하게 해결하기 위해서는

 

 

!힌트!인 휴리스틱 함수를 이용하는 것입니다!

 

 

 

그 힌트를 생각해보면

 

36만가지의 경우의 수를

 

확률이 높은 부분만 추리는 것입니다!

 

 

 

 

즉, Search Space를 줄이는 작업을 하는데,

 

 

tic-tac-toe게임의

 

큰 범위의 경우의 수는 다음과 같습니다.

 

 

tic-tac-toe게임의 경우는 다음과 같이 3가지로, 이를 돌리면 모든 경우의 수가 나오는 것을 볼 수 있습니다.

 

 

 

 

여기서 다음 턴에

 

수(X)를 두어서 이길 수 있는 경우의 수는

 

다음과 같습니다.

 

상대방이 수를 둘 수도 있지만, 내가 이길 수 있는 확률을 계산한 것입니다.

 

 

 

 

그렇다면,

 

내가 이길 수 있는 경우의 수가 큰

 

두 번째인 4로 가는것이

 

유리하겠죠?

 

 

 

이것을 함수로 정의한 것이

 

휴리스틱 함수인 h(n)입니다!

 

 

 

 

즉,

 

다음과 같이 표현할 수 있습니다.

 

휴리스틱 함수인 h(n)은 자신이 정의할 수 있습니다!! 쉽죠?

 

 

 

따라서 tic-tac-toe게임에서

 

휴리스틱 함수인 h(n)은

 

다음과 같이 정의했다고 볼 수 있습니다.

h(n)
= number of winning line (이길 수 있는 숫자)
: 이길 가능성에 대한 추정값

 

 

 

 

이 h(n)을 이용한다면

 

36만가지의 경우의 수를 모두 해야만 했던

 

첫 번째 그림을

 

이렇게 추려서

 

표현할 수 있습니다.

 

출처: https://www.slideserve.com/boettcher/heuristic-search-powerpoint-ppt-presentation

 

 

이길 확률이 제일 높은 4로 간 다음

 

다시 h(n)을 계산하는 겁니다.

 

 

이렇게 한다면

 

모든 노드를 탐색하지 않고,

 

이길 수 있는 확률에 근접하게 접근할 수 있겠죠?

 

 

 

 

하지만,

 

출발 노드에서 시작해서

 

목표노드까지 도달하는

 

최적의 경로를 탐색하는 것은

 

보장되지 않습니다.

 

 

 

 

그래서 이를 해결하기 위해서는

 

그림에서의

 

 

g(n)까지 모두 활용한

 

A* 알고리즘을 활용합니다!

 

 

 

 

다음 시간에는

 

이 A* 알고리즘에 대해

 

자세히 살펴보도록 하겠습니다. ˙ᵕ˙

 

 

 

 

 

 

 

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

 

:)