Hill  Climbing

낯선 영역에서 사람들이 쓰는 매우 흔한 문제 해결 방법은 현재 상태와 목표 상태간의 차이를 줄이는 것이다. 인간은 문제해결 (Problem Solving) 을 할 때 자주 차이감소법 (difference reduction, 현재상태와 목표상태의 차이를 줄여서 목표에 접근하는 방법) 또는 그 반대인 유사성 (similarity, Nearest neighbour) 에 의해 똑같이 강한 영향을 받는다. 그들은 차이를 줄여서 현재 상태보다는 목표 상태와 더 가깝게 닮은 새 상태로 현재 상태를 바꾸는 조작자들을 택한다..... 차이 감소를 때로는 언덕 오르기 (hill climbing) 라고 부른다. 만일 목표가 땅에서 가장 높은 지점이라고 상상할 때, 거기에 도달하는 방법은 항상 위로 올라가는 단계를 밟는 것이다. 목표와 현재 상태 간의 차이를 줄이면서 문제 해결자는 목표를 향해 '더 높은' 단계를 밟아가고 있다. 언덕 오르기는 길을 계속 따라가다 보면 가장 높은 지점 (global maximum) 인 목표보다 낮은 어떤 언덕의 꼭대기에 도달하게 될지도 모른다는 잠재적 위험을 갖고 있다 (local maxima (maximum 의 복수형)). 따라서, 차이 감소가 문제 해결을 보장하는 것은 아니다. 그것은 다음 단계의 향상 여부만을 고려하고 더 큰 계획의 달성 여부는 고려하지 않는 근시안적 방법이다. ..... 수단목표 분석 (Means Ends Analysis) 은 더 총체적인 시각을 문제 해결에 도입하려는 시도이다 ...... (John R. Anderson 1995)

어떤 문제는 명시적인 목표 조건 대신에 자료 구조에 대한 함수 가 있고, 이 함수가 최대 (혹은 최소) 가 되는 자료 구조를 찾고자 하는 경우가 있다. 하나의 자료 구조를 공간에 있는 하나의 점이라고 생각하면, 이 함수는 이 공간상의 지형 (land-scape) 이라고 할 수 있다. 이 지형을 돌아다니면서 고도가 높은 점을 찾는 일련의 방법들이 있다. 이 경우 전역 최대값 (global maximum) 을 모르기 때문에 고도가 최대인 점에 다달았는지 확실하게 알 수 없다 ............. 공간을 돌아다니는 기법 가운데 언덕 오르기 (hill-climbing) 방법은 한 점에서 고도가 가장 높은 인접한 점으로 이동하면서 다니는 것이다. 언덕 오르기 방법은 보통 현재의 점보다 높은 고도를 가진 인접한 점이 없으면 종료된다. 따라서 지역 최대값 (local maxima) 에 걸릴 수 있다 ........... (Nils J.Nilsson 1998)

Hill climbing search : Demo (★★★) : 이것은 깊이우선 탐색 (Depth First Search) 에 기초한다. 탐색 효율을 높이기 위해 휴리스틱 (Heuristic) 이 사용된다. 각 단계에서 선택한 것이 다른 것보다 더 나은지를 측정하고 계속해서 다른 선택을 한다. 알고리즘은 다음과 같다

root node를 queue Q 에 넣어 첫 번째 요소로 한다. 이후 깊이우선 탐색을 수행한다.
Q 가 비어 있든가 목표에 이를 때까지 수행한다. Q 에 있는 첫 번째 요소가 목표 (remaining distance 가 0 인 상태) 인지를 결정한다. 만일 목표가 아니라면 Q에서 첫 번째 요소를 제거하고, 그 자식노드들을 잔여거리 (remaining distance) 에 따라 sort하고, sort 된 리스트를 Q 의 앞쪽에 배치한다. 목표가 아닌상태에서 자식노드가 없으면 부모노드로 간다.
만일 목표에 도달하면 성공이며, 그렇지 않으면 실패이다.

Hill climbing 방법의 단점은 유사한 상황이 생길 수 있다는 것이다. 즉 작은언덕 (foothill)에서 시작할 경우는 거기서 너무 많은 시간을 소비하여 목표에 이르지 못할 것이다. 또한 고원의 평지 (plateaus) 와 같은 평탄한 곳에서는 비교할 대상을 찾지 못해 어떤 방향으로 가야할지를 결정못해 목적없이 방황할 수 있다. 어느 완만한 산등성이 (ridge) 에서는 목표인지 알고 내려올 수도 있겠지만 그것이 정상은 아니다.

Hill climbing 방법은 완전탐색 (complete search) 이다. 다양한 탐색방법 중에서 어떤 것이 가장 효율성을 증가시켜 search cost를 낮출 수 있는지는 모르나 heuristic 은 Hill climbing 방법의 단점을 보완해줄 좋은 방법이다. 즉 Hill climbing 은 상태공간에서 가장 효율적인 경로를 반드시 찾게 해주는 것은 아니다.

탐색 (Search)   깊이우선 탐색 (Depth First Search)   휴리스틱 (Heuristic)

차이 감소법 (Difference Reduction) : John R. Anderson

함수 최적화 (Function Optimization) : Nils J.Nilsson