개요
Local search란 Heuristic Search를 사용하여 탐색하는 방법중 하나를 말한다. 지역 탐색은 여러개의 답이 될 수 있는 후보중에서 적절한 시간안에 구할 수 있는 최적의 해를 구하고자 한다. 지역 탐색은 현재의 상태를 바탕으로 조금씩 수정해 나가면서 최적의 해를 찾는 알고리즘이다. Local search 알고리즘은 답을 찾기 위한 속도는 신경쓰지는 않지만 무수의 많을 수 있는 해의 집합에서 합리적인 해를 언젠가는 도출해 낼 수 있다는 장점이 있다. 또한 Local Search알고리즘은 적은 메모리 공간 즉 Space Complexity가 작다는 장점이 있다.
알고리즘
- 현재 상태를 조금이라도 괜찮은 상태로 바꾼다.
- 지금 이상태가 주어진 최적의 경우인지 확인한다.
- 아니면 다시 1로
예시
- [TSP]: 여러개의 도시를 모두 방문 할 수 있는 최적의 방법은 무었인가?
- [N-Queen Problem]: 체스판에서 8개의 퀸을 서로 공격받을 수 없는 위치에 배치하는 해를 구하라.