Hill climbing 문서 원본 보기

[[분류: 경로 탐색]]
[[분류: 탐색]]

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

== 알고리즘 ==
# Possible solution을 구한다.
# 정답인지 확인한다.
# 아니면 1로 돌아간다.

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