휴리스틱 탐색

휴리스틱 탐색은 시간이나 정보가 부족하여 합리적으로 판단할 수 없거나 굳이 체계적이고 합리적으로 판단할 필요가 없는 경우 어림으로 탐색하는 방법이다.

언덕오르기 방법,  A*알고리즘 , 최상 우선 탐색 ,빔 탐색이 있다.

언덕 오르기 기법은 적합도 검사를 통하여 주변 값을 탐색하여 적합도를 높이는 방법으로 해를 찾아간다.

빔 탐색은 적합도가 우수한 특정 개수의 노드만 확장하여 메모리에 관리하면서 목표 상태를 찾아 나가는 방법을 말한다.

A*알고리즘 앞으로의 경로와 함께 지금까지 온 경로도 고려하여 최단 경로로 해를 찾는 방법이다. 목표 상태까지 남은 경로는 정확히 계산할 수 없으므로 비용 추정 함수를 사용한다.

휴리스틱 탐색큰 내비게이션, 열차 스케줄링, 게놈 분석 등에 활용된다.



TSP와 휴리스틱 알고리즘

순회 세일즈맨 문제는 세일즈맨이 어떤 한 도시에서 출발하여 다른 도시를 1회씩만 방문하고 다시 출발했던 도시로 돌아오는 여행 경로의 거리를 최소화하는 문제이다.

무조건 탐색에서는 모든 지점이 연결되어 있을 경우

동적 프로그래밍에서는

분기 한정법에서는

한계 값이 가장 작은 노드의 자식 마디를 먼저 탐색한다.
최소의 최종 값보다 작은 한계 값을 갖고 있는 상위 노드가 있다면 그 마디의 자식 마디도 탐색한다.