Local search and optimization

이전까지의 search : 탐색공간의 체계적인 탐색
Local search : 한개 또는 그 이상의 현재상태를 평가하고 수정함 고려해야 할 건 cost가 아니라 solution state이다
local search는 최적화 문제를 풀기에 적합하다
state space는 완전한 구성의 집합
- e.g. 8개의 퀸이 전부 올려진 체스판
objective function h(s)에 따라 best state를 찾는다
- e.g. h(s) = number of conflicts
많은 최적화 문제는 standard search model에 적합하지 않다
local search = 현재상태를 킵하고 퀄리티를 높이는 쪽으로 갈 수 있는 이웃 상태를 찾아본다
장점
- 적은 메모리 사용량
- 엄청나게 크거나 무한대인 state spaces 안에서 합리적인 solution을 찾기 좋다
  - ↔ systematic algorithm

Hill-climbing search

값을 증가시키는 쪽으로 연속적으로 움직이는 루프
- 동률이면 아무거나 고름
- 더 높은 값의 이웃이 없는 peak에 도달했을 때 끝남
- (기억력은 떨어지는데) 안개 자욱한 에베레스트를 올라가는 것과 비슷하다
a.k.a. greedy local search, steepest ascent/descent