트리 탐색의 결과로 전역 최적값이 보장되는 기법은? | [7급 국가직 인공지능] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 인공지능] 23년 1회차
트리 탐색의 결과로 전역 최적값이 보장되는 기법은?
1
너비 우선 탐색(breadth-first search)
2
허용성(admissibility)을 갖지 않는 알고리즘3
언덕 오르기 방법(hill climbing method)
4
탐색 깊이 제한이 있는 깊이 우선 탐색(depth-first search)
해설
트리 탐색에서 최적해가 보장되는 기법은 너비 우선 탐색이다.
너비 우선 탐색은 얕은 깊이부터 노드를 빠짐없이 확장하므로 해가 있으면 반드시 찾고, 간선 비용이 같으면 가장 먼저 찾은 얕은 해가 곧 최적해가 된다.
- 허용성이 없는 : 휴리스틱이 실제 비용을 과대평가할 수 있어 최적 경로를 놓칠 수 있다.
- 언덕 오르기: 더 나은 이웃으로만 이동하는 지역 탐색이라 지역 최적값에 갇힐 수 있다.
- 깊이 제한 깊이 우선 탐색: 해가 제한 깊이보다 깊으면 찾지 못하고, 먼저 찾은 해가 최적이라는 보장도 없다.
오류나 개정된 내용이 보이면 알려주세요