Skip to main content

더 높은 언덕을 오르는 방법

김욱영

언덕오르기 알고리즘 중 지역 최대값을 갖는 경우 - Hill climbing

컴퓨터 과학의 고전적인 알고리즘 문제 중 언덕오르기 문제가 있다. 어떻게 생겼는지 파악할 수 없는 지형에서 어떻게 하면 가장 높은 언덕에 오를 수 있을까?

이에 대한 가장 간단한 알고리즘은, 모든 순간에서 더 높은 방향으로 발을 내딛는 것이다. 이 방법에 문제점은 가까이 있는 언덕 자체가 낮은 경우 가장 높은 언덕이 아닌, 낮은 언덕 꼭대기에 이르게 된다는 점이다.

이 위험을 해소하기 위해 걷기에 임의성을 추가하면 된다. 많은 무작위성에서 시작하고, 시간이 지남에 따라 무작위성의 양을 줄이면, 더 큰 언덕 근처에서 이동할 가능성이 커진다.

또 다른 방법은 무작위 지형에 반복적으로 시작하여, 언덕 등반을 한 후에 뒤로 물러서서 어느 언덕이 가장 높은지 결정하는 것이다. 더 높은 위치에서는 안개가 덜 낀 시야로 더 높은 언덕을 볼 수 있기 때문이다.

이는 커리어를 결정할 때도 동일하게 이용된다.

우선은 모든 순간에 더 성장할 수 있는 방향으로 발을 내디뎌야 한다. 처음에는 높은 무작위성으로 커리어를 성장시키고, 점점 무작위성을 줄여야 한다. 그러면 더 높은 위치에 있을 수 있게 된다.

또 다른 방법은 많은 커리어를 경험한 후, 구직자로 돌아가서 가장 희망하는 커리어를 결정하는 방법이다. 이미 몇 개의 커리어를 올라가 보았기에 그 커리어에서 더 높은 위치를 볼 수 있다.

구불구불하게 걷고, 새로운 곳에 무작위로 뛰어들어야 한다. 그리고 가장 높은 가장 높은 곳을 찾았을 때 그 곳을 향해 발을 내디뎌야 한다.

참고자료 : cdixon | Climbing the wrong hill