역추적은 해결해야 할 문제, 부분 후보의 특성 및 전체 후보로 확장되는 방법을 정의하는 사용자가 지정한 ”블랙박스 절차”에 따라 달라집니다. 따라서 다른 많은 메타 휴리스틱과 달리 제한된 시간 내에 유한 한 문제에 대한 모든 해결책을 찾을 수 있지만 특정 알고리즘보다는 메타 휴리스틱입니다. 역추적은 일부 계산 문제, 특히 제약 조건 만족도 문제, 솔루션에 대한 후보를 점진적으로 구축하고 후보(”역추적”)를 포기하는 일부 계산 문제에 대한 모든(또는 일부) 솔루션을 찾는 일반적인 알고리즘입니다. 유효한 솔루션으로 완료할 수 없다고 판단합니다. [1] [2] 역추적은 크로스워드, 구두 산술, 스도쿠 및 기타 여러 퍼즐과 같은 제약 조건 만족도 문제를 해결하는 데 필수적입니다. 또한 배낭 문제를 해결하고 텍스트 및 기타 조합 최적화 문제를 구문 분석하는 데에도 사용됩니다. 역추적은 선택적 트리/그래프 통과 방법으로 생각할 수 있습니다. 트리는 일부 초기 시작 위치(상위 노드)와 최종 목표 상태(나뭇잎 중 하나)를 나타내는 방법입니다. 역추적을 통해 원시 무차별 대입 접근 방식이 불가능한 수의 선택으로 폭발할 수 있는 상황을 처리할 수 있습니다. 역추적은 일종의 정제된 무차별 대입입니다.

각 노드에서 분명히 불가능한 선택 사항을 제거하고 잠재력이 있는 노드만 재귀적으로 검사합니다. 이렇게 하면 트리의 각 깊이에서 나중에 고려해야 할 선택 항목의 수가 줄어들입니다. 역추적은 제약 조건 만족도 문제를 해결하는 데 중요한 도구입니다[3] 크로스 워드 퍼즐, 구두 산술, 스도쿠, 그리고 다른 많은 퍼즐. 배낭 문제 및 기타 조합 최적화 문제에 대해 구문 분석하는 데 가장 편리한 기술(가장 효율적인[인용필요])이 되는 경우가 많습니다. 또한 아이콘, 플래너 및 프롤로그와 같은 소위 논리 프로그래밍 언어의 기초이기도합니다. 역추적은 ”부분 후보 솔루션”의 개념을 인정하는 문제와 유효한 솔루션으로 완료할 수 있는지 여부를 비교적 빠르게 테스트하는 문제에 대해서만 적용할 수 있습니다.

backtracking 예제