1 What is heuristic search?
: 경험칙(휴리스틱)에 따라 명백히 잘못된 방안을 제거해 탐색 공간을 좁히는 것을 휴리스틱 탐색 이라고 한다.
2 Uninformed vs. informed search
- 무정보 검색: 경로를 선택할 때 사전에 주어진 정보나 규칙을 이용하지 않으며 모든 경로를 따져보고 적합한 것을 추려내 최적의 경로를 도출하는 방법
- 정보 검색: 사전에 주어진 정보나 규칙을 이용해 모든 경로를 따져보지 않고 최적의 경로를 도출하는 방법 ex) 휴리스틱 탐색
3 Constraint Satisfaction Problems
: 문제를 해결하는 과정에서 어기지 말아야 할 조건이나 규칙인 제약 조건이라 하고 이것이 주어진 문제를 제약 조건 문제라고 한다.
4 Local search techniques
: 지역 탐색 기법은 제약 조건 문제를 푸는 휴리스틱 알고리즘 중 하나로 모든 제약 조건이 만족할 때까지 변수의 값을 계속 업데이트하는 기법이다. 값을 업데이트할 때마다 특정 함수를 통해 품질을 측정하고 그 값을 할당 비용이라 한다. 지역 탐색의 목표는 각 단계마다 최소 비용으로 업데이트하는 것이다. ex) 언덕 오르기
5 Simulated annealing
: 시뮬레이티드 어닐링 기법은 지역 탐색 기법이자 확률 탐색 기법이다. 언덕 오르기 기법을 변형한 것으로 골짜기를 내려가는 방식으로 문제를 처리한다. 탐색 방향은 목적 함수로 결정하고 이 함수가 바로 휴리스틱 역할을 한다. 골짜기를 내려가는 속도는 어닐링 스케쥴이라 하는데 이 값이 너무 크면 국소적 최대점에 빠지기 때문에 크기를 잘 조절해야 한다.
1 현재 상태가 목표점인지 확인한다.
2 맞다면 멈추고, 아니라면 최적 상태 변수를 설정한다.
3 어닐링 스케쥴을 정의한다.
4 현재 상태와 새 상태의 차이를 계산한다.
5 새로운 상태가 현재 상태보다 낮으면 이를 현재 상태로 정의하고 미리 정의된 확률값을 할당한다.
(+ 이 값은 난수 생성기로 생성하며 임계값에 따라 판단한다.)
6 값이 임계값보다 높으면 현재 상태를 최적의 상태로 설정한다.
7 노드 개수에 따라 어닐링 스케쥴을 업데이트하고 목표에 달성할 때까지 이 과정을 반복한다.
+) 그리드 탐색, 제약 조건 문제, 영역 칠하기, 8-퍼즐, 미로 찾기
