(새 문서: 분류: Path Finding 분류: 탐색 == 개요 == Hill Climbing은 현재 상태를 더 좋은 상태가 발견되면 그 지점으로 조금씩 움직이는 방식으로 현재의 해보다 더 좋은 최적의 해를 찾아서 조금씩 움직이는 알고리즘을 말한다. 현재의 상태만을 저장한채, 바로 다음 단계의 예측만을 바탕으로 정답을 향해서 나아간다. 여러개의 변종이 있으며 현재의 상황보다 조금이라도 좋...) |
편집 요약 없음 |
||
| 1번째 줄: | 1번째 줄: | ||
[[분류: | [[분류: 경로 탐색]] | ||
[[분류: 탐색]] | [[분류: 탐색]] | ||
2023년 2월 24일 (금) 09:06 기준 최신판
개요
Hill Climbing은 현재 상태를 더 좋은 상태가 발견되면 그 지점으로 조금씩 움직이는 방식으로 현재의 해보다 더 좋은 최적의 해를 찾아서 조금씩 움직이는 알고리즘을 말한다. 현재의 상태만을 저장한채, 바로 다음 단계의 예측만을 바탕으로 정답을 향해서 나아간다. 여러개의 변종이 있으며 현재의 상황보다 조금이라도 좋으면 그 상태로 이동하는 Simple Hill Climbing, 현재의 상태를 바탕으로 갈 수 있는 모든 상황중에서 최고의 해로 나아가는 Steepest Ascent Hill Climbing 그리고 가끔씩 random한 움직임을 더하는 Stochastic Hill Climbing이 있다.
알고리즘
- Possible solution을 구한다.
- 정답인지 확인한다.
- 아니면 1로 돌아간다.
특징
- Complete한 알고리즘이다. (답을 구하기는 한다.)
- Optimal하지는 않다. (최고의 답이 아닐 수 있다.)