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

반갑습니다 :-)

 

 

오늘은 탐색(Search)에 대해 알아보도록 하겠습니다.

 

 

 

어떠한 문제를 해결하고자 할 때,

 

1. 문제를 표현 (변환)

2. Search 전략 (적용)

 

과 같은 순서로 진행됩니다.

 

 

(Problem Solving As Search?

 

1. Problem RepreSentation

2. Search Algorithm)

 

여기서 말하는

 

문제의 예시는 다음 그림으로 한다면,

 

 

 

문제(Problem)는

만약 Start에서 Goal로 가야한다면?

 

 

 

선을 따라서 이어가면 Goal을 찾을 수는 있지만,

 

한눈에 찾기는 힘듭니다.

 

 

 

그래서 이를

 

①Tree로 변환해줍니다.

 

 

 

그러면 Goal로 가는 경로가 쉽게 보이죠?

 

 

 

 

마지막으로

 

②탐색 알고리즘을 적용합니다.

 

 

 

탐색 알고리즘(Search Algorithm)의

 

종류는 크게 4가지가 있습니다.

 

앞으로 게시글에서 하나씩 살펴볼 예정입니다!

 

1. Uninformed Search
2. Informed Search
3. Local Search
4. Adversarial Search

 

 

---

여기서 간단한 특징은

 

Uninformed Search
Informed Search
Adversarial Search

 

은 Goal까지 가는 효율적인 경로를 찾는 것이고,

 

Local Search

 

은 Goal 자체를 찾는 것입니다.

 

 

 

 

 

이를 하나의 상태, state로 표현하면 다음과 같습니다.

 

Uninformed Search
Informed Search
Adversarial Search

1. 문제 : state로 표현, state space가 있음
2. 해결: inital state에서 goal state으로 가는 path 찾기
(goal state은 이미 알고 있음)

 1) 문제의 재구조화 (표현)
  - 탐색할 수 있는 형태로 표현
   -> tree형태가 가장 적합

 2) 탐색 알고리즘 적용
 - Uninformed Search (BFS, DFS, Best-FS)
  -> 단순 반복 탐색
 - Informed Search (휴리스틱)
  -> Uninformed Search의 시간문제를 해결
 - Adversarial Search

 

 

---

 

Local Search

1. 문제 : state로 표현, state space가 있음
2. 해결: inital state에서 조건에 맞는 goal state을 빠르게 찾기
(goal state은 모름)

 1) 문제의 재구조화 (표현)
 - state와 value로 표현
  -> object function, fitness function 등

2) 탐색 알고리즘 적용

 - Local Search (Hill Climbing, Simulated Annealing, Local Beam, Genetic)

 

 

 

앞으로 각 탐색 알고리즘에 대해 자세히 다뤄보도록 하겠습니다!

 

 

 

 

 

 

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

 

:)

 

 

 

참고문서: 정보적사고에서 인공지능까지, 김현철, 한빛미디어 2019