Hill climbing

개요

Hill Climbing은 현재 상태를 더 좋은 상태가 발견되면 그 지점으로 조금씩 움직이는 방식으로 현재의 해보다 더 좋은 최적의 해를 찾아서 조금씩 움직이는 알고리즘을 말한다. 현재의 상태만을 저장한채, 바로 다음 단계의 예측만을 바탕으로 정답을 향해서 나아간다. 여러개의 변종이 있으며 현재의 상황보다 조금이라도 좋으면 그 상태로 이동하는 Simple Hill Climbing, 현재의 상태를 바탕으로 갈 수 있는 모든 상황중에서 최고의 해로 나아가는 Steepest Ascent Hill Climbing 그리고 가끔씩 random한 움직임을 더하는 Stochastic Hill Climbing이 있다.

알고리즘

1. Possible solution을 구한다.
2. 정답인지 확인한다.
3. 아니면 1로 돌아간다.

특징

1. Complete한 알고리즘이다. (답을 구하기는 한다.)
2. Optimal하지는 않다. (최고의 답이 아닐 수 있다.)