[인공지능] Informed Search (+ Uninformed Search 기법 비교)

반갑습니다. :)

 

 

오늘은 Informed Search에 대해서 살펴보도록 하겠습니다.

 

 

 

 

그. 전. 에!

 

저번 글까지 Uninformed Search에 대해서 알아보았는데,

 

 

3가지의 기법을 잠깐 비교하고 

 

Informed Search에 대해 살펴보도록하겠습니다.

 

( ᐛ )و

 

 

 

 

 

---

 

Uninformed Search

 

Uninformed Search의

 

많이 알려진

 

총 3가지 기법을 살펴보았습니다!

 

 

https://setori-dev.tistory.com/44?category=517812

[인공지능] Uninformed Search

 

 

 

 

 

BFS, DFS, UCS의 특징을

 

표로 정리하면 다음과 같습니다.

 

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

 

 

 

간결히 보면

 

DFS는 성능적인 측면에서 가장 좋지 않고,

 

 

그나마 BFS를 기반으로 만들어진

 

UCS도 Time Complexity(시간복잡도)를

 

해결하지 못하는 것을 볼 수 있습니다.

 

 

 

 

시간복잡도를 수학적인 식으로 계산하여

 

디테일하게 비교할 수 있지만,

 

 

 

간단히 말하면

 

Uninformed Search의 정답(Goal)은

 

언젠가 찾는 다는 것을 보장(Completeness)하지만,

 

 

그 '언젠가'가 50년이 걸릴 수도

 

정답을 못보고 갈 수도 있다는 것입니다.

 

 

 

 

즉,  Uninformed Search의 시간복잡도를

 

Informed Search가 완벽하게 해결할 수는 없지만,

 

좀 더 빠르게

 

내가 정답을 볼 수 있는 시간대만큼

 

줄이는 것입니다!

 

 

 

이해 되셨나요? ◡̈⋆*

 

 

 

 

 

 

그래서 오늘은!

 

 

인공지능의 [문제해결] 영역,

 

탐색 전략의 두 번째,

 

 

 Uninformed Search의 시간복잡도 문제를

 

해결 할 수 있는 탐색 기법인

 

Informed Search을 살펴보도록 하겠습니다!

 

 

 

 

Informed의 뜻은

 

Uninformed의 반대로

 

지식이 있는, 정보를 가지고 있다 입니다.

 

 

 

 

즉,

 

Informed Search란

 

문제를 해결하기 위한 어떠한 힌트나 정보를 가지고

 

이를 기반으로 탐색하는 기법입니다.

 

 

 

 

 

 

---

 

일단 탐색하기 전!

 

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

[인공지능] 탐색 전략(Search)

 

 

에서

 

우리가 눈으로 찾을 수 있는 이 경로를

 

컴퓨터가 찾을 수 있도록 하는

 

Informd Search의 종류에 대해서 살펴보도록 하겠습니다.

 

 

 

 

 

---

 

 

Informd Search

 

 

 

 

 

앞서 Uninformed Search와 동일하게

 

 

 

다음 Tree에서 밑으로 뻗은 것을

 

가지, 노드(node) 또는 fringe라고 합니다.

 

 

 

 

다양한 방법 있을 때

 

밑으로 fringe가 확장(Expansion)됩니다.

 

 

 

 

이렇게 확장된 fringe에서

 

Goal을 찾기위해 탐험(Explore)하는 작업입니다.

 

 

 

 

즉,

 

Informd Search을 할 때

 

Main Question은

 

어떤 fringe을 가지고 탐색(Explore)을 할지

 

Exploration strategy를 가지는 겁니다.

 

 

 

 

이때!

 

Uninformed Search와는 달리

 

정답(Goal)로 가는

 

힌트(hint)를 가진채로 진행됩니다!

 

 

 

 

 

Main Question

: Exploration strategy

(!힌트를 가진 채! fringe 중 어느 것을 골라 Goal이 인지 아닌지 테스트 하는 전략)

 

 

 

 

Uninformed Search의 시간복잡도를

 

비교적으로 해결할 수 있는 Informed Search의 기본적 구조는 다음과 같습니다.

 

 

정답인 G로 가기 위한 경로, m은 현재점을 가정

 

만약,

 

트리(Tree)가 너무 클 경우

 

G인 Goal로 가는 경로를 찾는데에

 

많은 시간이 걸릴 것 입니다.

 

 

 

 

그래서 Informed Search는

 

힌트를 가지고 경로를 탐색하는데

 

 

 

이 힌트를

 

domain knowledge라고 하며

 

그 유명한 휴리스틱이라고도 부릅니다.

 

 

domain konwledge

= 경험적 지식
= 휴리스틱 (heuristic)
= 힘트

 

 

다시

 

위 그림에서

 

현재상태인 m fringe까지 UCS로 값을 정하고

 

이를 g(n)이라고 합니다.

 

 

 

그 다음

 

m에서 g로 가는 경로를

 

휴리스틱 즉, 추정값을 정하고

 

이를 h(n)이라고 합니다.

 

 

 

 

정리하면 다음과 같은 그림입니다!

 

 

 

 

 

많은 종류 중,

많이 알려진 2가지 탐색 기법을 살펴보고자 합니다.

 

 

 

 

1. Best-first Search

 

 

2. A* Search (에이스타 알고리즘)

 

 

 

 

 

 

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

 

:)