최근에 A * 검색 알고리즘과 같은 경험적 알고리즘을 배우고 있습니다. f (n) = g (n) + h (n)과 같은 휴리스틱 검색 알고리즘에 대한 몇 가지 기본 사실을 알고 있으며, 또한 각자가 받아 들일 수 있고 일관성있는 것이 무엇인지 알고 있습니다. 하지만 나를 혼란스럽게하는 것은 휴리스틱 알고리즘이 어떻게 작동 하는가? 휴리스틱 값이 실제 비용 값에 더 가깝다면 더 좋은 이유는 무엇입니까? 감사!휴리스틱 알고리즘은 어떻게 작동합니까?
완벽한 휴리스틱 h (n)에 대해 생각하십시오. n에서 목표까지의 최단 거리를 제공합니다.
그러므로 최단 경로상의 각 노드 s에 대한 비용 함수 f (s)는 같으며 최단 경로 길이와 같습니다. 거리까지의 거리와 목표까지의 최단 거리입니다.
그래서 최단 경로 노드 s와 주어진 최단 경로 노드 n에 대해 우리는 f (s) < f (n)를 갖습니다.
이제는 A * 알고리즘이 이러한 추론과 함께 작동하는 방식에 대해 생각해보십시오. 각 노드에서 큐에 확장 할 다음 노드가 최단 경로의 다음 노드가됩니다. 가능한 한 작은 값이어야하기 때문입니다 f. 따라서 알고리즘은 실수가없는 최단 경로를 따라 처음부터 목표 노드로 직접 이동합니다!
완벽한 휴리스틱이없는 경우 f (n) < f (s)가 가능하기 때문에 알고리즘이 실수로 오류를 만들 수 있으므로 알고리즘은 불필요한 분기를 따라 "최단 경로에서 벗어날 수 있습니다".
알고리즘의 장점은 휴리스틱이 허용되는 한 최단 경로를 찾으며 완벽한 경로보다 느린 것입니다.
경험적 방법은 훌륭한 교육을받은 것입니다. 근사값은 일정 범위 내에 있음을 보장합니다. christofides 알고리즘은 근사 알고리즘이지만 삼각형 부등식 (metric tsp)을 만족하는 그래프로만 작동합니다. 출처 : https://cs.stackexchange.com/questions/10182/difference-between-heuristic-and-approximation-algorithm
경험적 함수는 종단 간 경로를 마치는 데 남은 가장 낮은 비용에 대한 예상치처럼 작용합니다. f(n) = g(n) + h(n) 하단에서 최소 비용으로 연장하고 완료하려면 g(n) 경로. 따라서 허용 가능한 휴리스틱 함수의 경우 검색이 성공할 것이라고 보장됩니다.
휴리스틱 함수가 가까울수록 검색 속도가 빠릅니다. 극단적 인 경우를 생각하면 h(n) = 0, 대신에 A 검색을 사용하고, h(n)이 정확히 나머지 값인 f(n)이 실제 비용이면 검색이 완료된 것입니다.