휴리스틱 탐색 및 지역 탐색

수강일시: 2021.01.17

출처: kmooc SNU048

 

 

www.kmooc.kr/courses/course-v1:SNUk+SNU048_011k+2020_T2/course/

강좌 | SNU048_011k | K-MOOC

 

이번수업에선 informed search방식에 대해 알아보았다.

 

최소한의 필요정보만 주어진 uninformed search와 다르게 informed search는 추가 정보를 이용하여 효율적인 탐색을 진행하도록 한다. 이전 강의에서 본 루마니아 예제에서 본다면 어떤 노드로 가는것이 바람직한 것인가에 대한 판단이 들어가게 된다.

 

 

1.best search

Greedy best 는 가장 cost가 낮은것을 우선적으로 탐색하는 방식이다.

즉 f(n)=h(n) (h는 비용)

다음으로는 A star search이다.

A star는 기존에 들어간 비용에 추가로 예상되는 비용을 생각하여 최단거리를 찾아 가는 방식이다.

 

h가 admissible 하면 optimal하다.

 

 

 

 

 

 

 

 

 

다음으로는 local search를 보도록 하겠다.

예시-nqueen

reminder-by-kwan.tistory.com/51

백준 9633번 NQueen 파이썬 (python code)

다만 여기서는 다른 문제해결 전략을 선택했다.

hill-climbing search는 매번 답에 가장 가까워지는것으로 보이는(기울기가 가장 높은) 길을

greedy하게 선택하는 방법이다.

다만 local maximum 에 빠지는 일이 발생한다. 이를 방지해야 한다.

 

이를 위의 n queen문제에 적용해보도록 하자.

임의로 queen을 놓고 h값을 최대한 많이 감소시키는 움직임을 h==0이 될때까지 지속한다.

 

 

하지만 여기서 단점은 초기 상태에 따라 h가 0이 될 수 없는 경우도 존재한다.

이러한 문제를 해결하기 위한 방안으로 simulated annealing search를 보도록 하자.

즉, h값을 최대한으로 감소시키는것 이외에 추가적인 움직임을 허용하여 탐색하는 과정이다.

random move를 추가하여 탐색 속도는 조금 더 걸리더라도 원하는 결과를 얻을 확률이 높아진다.

ml/ dl에서 많이 언급하는 안장점에 빠지지 않기 위한 방법중 하나라고 볼 수도 있다.