728x90
언덕 오르기 탐색 hill climbing search
- 깊이 우선 탐색 depth first search에 기초하며, 탐색 효율을 높이기 위해 휴리스틱이 사용
-> 각 단계에서 선택이 다른것보다 나은지 측정하고 계속하여 다른것을 선택
언덕 오르기 탐색 알고리즘
1. 루트 노드를 큐 q에 넣어 첫번째 요소로 한다. 이후 깊이 우선 탐색 수행
2. Q가 비어있거나 목표를 이룰때 까지 수행. Q에 있는 첫번째 요소가 목표 (remaining distance가 0인 상태) 인지를 결정
-> 목표가 아니라면 Q에서 첫 번째 요소를 제거하고, 그 자식 노드들을 잔여 거리 remaining distance에 따라 정렬하고, 정렬된 리스트를 Q 앞쪽에 배치. 목표가 아닌 상태에서 자식 노드가 없으면 부모노드로 간다.
3. 목표 노드에 도달하면 성공, 아니면 실패
언덕 오르기 방법 단점
- 유사한 상황의 발생 가능성이 있음
- 작은 언덕 foothill에서 시작시 거기서 너무많은 시간을 소비함
- 고원의 평지 plateaus와 같이 평탄한 곳에서 비교대상을 찾지 못해 어느 방향을 갈지 못하여 방황할수 있음
언덕 오르기 방법의 특징
- 완전 탐색 complete search
- 다양한 탐색방법중 어느것이 효율성을 증가시켜 search cost를 낮출수 있을지는 모름
- 휴리스틱이 언덕 오르기의 단점을 보완해주는 좋은 방법
-> 언덕 오르기가 상태 공간에서 가장 효율적인 경로를 반드시 찾는것은 아님
300x250