근사 탐색

소개글

근사 탐색

목차

1. 서 론
2. 본 론
(1) 섬 구동 탐색 (island-driven search)
(2) 계층적 탐색 (hierarchical search)
(3) 시계 제한 탐색 (limited-horizon search)
(4) 순환

본문내용

근사탐색 (Approximate Search)

1. 서 론
근사 알고리즘은 최적의 해를 구하는 대신에 “충분히 좋은”해를 구한다. 근사 알고리즘은 정확하게 풀기에는 너무 많은 복잡한 문제를 풀어야 할 때 주로 사용된다. 예를 들어, “외판원 여행문제”를 들 수 있다.
몇 개의 도시를 방문해야 하는 외판원을 생각해보자. 외판원 여행 문제(Traveling Salesman Problem)의 목표는 모든 도시를 한 번씩 방문하고 처음에 출발한 도시로 돌아오는 가장 짧은 경로를 찾는 것이다. 외판원 여행 문제의 최적해를 구하는 것이 가능하기는 비싸기 때문에 근사 해를 구하기 위해 휴리스틱을 사용한다. 휴리스틱은 최적해를 구하기가 현실적으로 불가능할 때 최적은 아니지만 받아들일 만한 해를 구하는 것이다.
외판원 여행 문제에서 외판원이 방문해야 하는 도시를 격자상의 점으로 표현할 수 있다. 그리고 다음의 휴리스틱을 사용해서 점들간의 최단 경로를 구할 수 있다. 우선 외판원이 방문을 시작하는 점을 검정색으로 칠한다. 다른 점들은 경로에 포함되기 전까지는 흰색이고 경로에 포함되는 순간 검정색으로 바뀐다. 그리고 나서 모든 흰 점v에 대해 가장 최근에 검정색이 된 점 u와의 거리를 계산한다. U와 가장 가까운 점을 검정색으로 칠한다. 모든 점이 검정색이 될 때까지 이 과정을 반복하고 마지막에 여행을 시작한 점을 경로로 포함시키면 경로가 완성된다.

이와 같이 휴리스틱 탐색에서 언급한 것처럼 최적 계획을 만들어야 한다는 조건을 완화시키면, 많은 경우에 계획을 찾는 데 필요한 계산비용을 줄일 수 있다. 이런 비용 감소는 두 가지 방법으로 이루어질 수 있다. 첫째는, 목표까지의 경로를 최적이어야 한다는 조건 없이 찾는 것이다. 또 다른 방법은, 완전히 목표 노드까지 가지 않는 부분 경로를 찾는 것이다. 두 가지 방법 모두 A* 형태의 탐색을 사용할 수 있다.

참고 자료

없음