(새 문서: 분류: 탐색 == 개요 == Local search란 Heuristic Search를 사용하여 탐색하는 방법중 하나를 말한다. 지역 탐색은 여러개의 답이 될 수 있는 후보중에서 적절한 시간안에 구할 수 있는 최적의 해를 구하고자 한다. 지역 탐색은 현재의 상태를 바탕으로 조금씩 수정해 나가면서 최적의 해를 찾는 알고리즘이다. Local search 알고리즘은 답을 찾기 위한 속도는 신경쓰지는 않...)
 
편집 요약 없음
14번째 줄: 14번째 줄:


== 종류 ==
== 종류 ==
# [[Hill Climbing]]
# [[Hill climbing]]
# [[Simulated Annealing]]
# [[Simulated Annealing]]
# [[Beam Search]]
# [[Beam Search]]
# [[Genetic Algorithm]]
# [[Genetic Algorithm]]

2023년 2월 11일 (토) 03:09 판


개요

Local search란 Heuristic Search를 사용하여 탐색하는 방법중 하나를 말한다. 지역 탐색은 여러개의 답이 될 수 있는 후보중에서 적절한 시간안에 구할 수 있는 최적의 해를 구하고자 한다. 지역 탐색은 현재의 상태를 바탕으로 조금씩 수정해 나가면서 최적의 해를 찾는 알고리즘이다. Local search 알고리즘은 답을 찾기 위한 속도는 신경쓰지는 않지만 무수의 많을 수 있는 해의 집합에서 합리적인 해를 언젠가는 도출해 낼 수 있다는 장점이 있다. 또한 Local Search알고리즘은 적은 메모리 공간 즉 Space Complexity가 작다는 장점이 있다.

알고리즘

  1. 현재 상태를 조금이라도 괜찮은 상태로 바꾼다.
  2. 지금 이상태가 주어진 최적의 경우인지 확인한다.
  3. 아니면 다시 1로

예시

  1. [TSP]: 여러개의 도시를 모두 방문 할 수 있는 최적의 방법은 무었인가?
  2. [N-Queen Problem]: 체스판에서 8개의 퀸을 서로 공격받을 수 없는 위치에 배치하는 해를 구하라.

종류

  1. Hill climbing
  2. Simulated Annealing
  3. Beam Search
  4. Genetic Algorithm