언덕등반 탐색

개념

언덕등반 탐색은 현재 상태에서 가장 좋아 보이는 다음 상태 하나만 선택해 이동하는 휴리스틱 탐색 방법이다. Greedy 탐색의 한 형태로 볼 수 있다.

동작

현재 상태의 자식 상태들을 평가하고, 평가 함수 값이 가장 좋은 상태로 이동한다. 과거의 다른 후보들을 저장하지 않기 때문에 OPEN과 CLOSED를 사용하지 않는 방식으로 설명되기도 한다.

평가값이 클수록 좋은 문제라면 다음 상태는 다음처럼 선택한다.

$$s_{t+1}=\arg \underset{s^{\prime }\in N(s_t)}{\max }f(s^{\prime })$$

장점

간단하고 빠르다. 매번 가장 좋아 보이는 방향으로 이동하기 때문에 계산량이 적다.

한계

전체 최적해가 아니라 지역 최적에 갇힐 수 있다. 목표에 도달하려면 잠시 나빠지는 방향으로 가야 하는 경우에도 이동하지 못할 수 있다.