3주차 휴리스틱 탐색 및 지역 탐색 (3-2 지역 탐색)

3주차 휴리스틱 탐색 및 지역 탐색 (3-2 지역 탐색)

3주차 휴리스틱 탐색 및 지역 탐색 (3-2 지역 탐색)

지난 시간에는 추가 정보가 존재할 때 그 정보들을 이용해서 탐색하는 휴리스틱 탐색에 대해 알아봤습니다.

이번 시간은 지역 탐색에 관한 내용인데요.

요새 자주 들을 수 있는 딥러닝 기술이 바로 이 지역 탐색을 적극적으로 활용하고 있습니다.

각 경로의 비용을 계산해서 제일 합리적인 경로를 찾는 휴리스틱 탐색과는 다르게

지역탐색은 목표 자체를 찾는 것이 더 중요할 때 쓰입니다.

당장 현재 내가 어떤 상태에 있다고 할 때, 인접한 노드들 중, 현재 상태보다 낫다고 판단되는 곳으로 이동하는 것입니다.

하나하나씩 나아가는 방법이라고 생각하면 되겠죠.

지역 탐색의 장점

1. 메모리가 훨씬 적게 사용된다.

2. 전체 경로를 분석하는 데에 시간/비용을 낭비하지 않아도 된다.

-> 실제로 전체를 다 살펴보지 않아도, 생각보다 꽤 괜찮은 솔루션을 얻는 경우가 많다.

지역 탐색 방법들

1. Hill Climbing Search (언덕 오르기 탐색) : 매우 깊은 안개 때문에 가까운 주변만 살필 수 있는 상황이라고 가정

- 시야가 확보되지 않은 경우, 주변에서 가장 경사가 높은 곳으로 올라가게 됨

- Greedy search : 내가 지금 취할 수 있는 행동들 중 가장 좋은 행동을 취하는 방법

- 치명적인 단점 : Local Maxima에 빠질 수 있음

Local Maxima(지역 최대치)

Hill Climbing Search 예시 : n-queens problem (가로/세로/대각선에 2개 이상의 퀸이 놓이면 안되는 문제)

2. Simulated Annealing Search(담금질 기법) : Hill Climbing + Random Walk(무작위성)

- Hill Climbing Search에서는 절대 내려가는 선택을 하지 않기 때문에, Local Maxima에 빠질 수 있음

- 중간 중간에 무작위성을 넣으면 많은 경우에 Local Maxima를 피할 수 있음

- 처음에는 무작위성이 높지만, 갈수록 빈도를 줄임

강의만 들었을 때는 시뮬레이티드 어닐링이 뭔지 감이 잘 안왔습니다. 담금질이란 말도 와닿지 않구요.

여기서 중요한 개념은 '온도'인데요.

처음에 온도를 가장 높은 값으로 설정하고, 점점 온도가 내려가서 0이 되면 탐색을 중단합니다.

온도가 높을 때는 무작위성도 높아요. 여기 저기 뛰어다니며 값을 비교해 보는 거죠.

현재 상태에서 최적의 상태를 찾고, 무작위로 다른 선택을 합니다. 그리고 둘 중 어떤 것을 선택할지 고르죠.

하지만 이 무작위 선택의 범위가 온도가 내려갈 수록 점점 좁아진다고 생각하면 됩니다.

초반에는 위험을 감수할 확률이 높지만, 갈 수록 위험을 감수하지 않으려고 하는 거죠.

3주차부터 잘 이해되지 않는 내용이 나와버렸네요..ㅠㅠ

따로 공부를 조금 해야겠습니다!

from http://data-learning-jjoshu.tistory.com/8 by ccl(A) rewrite - 2021-12-08 11:00:49