차례:
정의-역 추적이란 무엇입니까?
역 추적은 특정 계산 문제에 대한 일부 또는 모든 솔루션을 캡처하기위한 알고리즘이며, 특히 제약 조건 만족 문제에 대한 것입니다. 이 알고리즘은“부분 후보 솔루션”개념을 수용 할 수있는 문제에 대해서만 사용할 수 있으며 후보 솔루션이 완전한 솔루션이 될 수 있는지 여부를 신속하게 테스트 할 수 있습니다. 역 추적은 제약 만족 문제와 퍼즐을 해결하는 중요한 기술로 간주됩니다. 또한 구문 분석을위한 훌륭한 기술로 간주되며 많은 논리 프로그래밍 언어의 기초를 형성합니다.
Techopedia는 역 추적을 설명합니다
역 추적은 첫 번째 하위 문제에 대한 솔루션을 찾은 다음 첫 번째 문제의 솔루션을 기반으로 다른 하위 문제를 재귀 적으로 해결함으로써 전반적인 문제를 해결하는 데 도움이됩니다. 현재 문제를 해결할 수 없으면 단계가 역 추적되고 다음 가능한 솔루션이 이전 단계에 적용된 후 계속 진행됩니다. 실제로 역 추적의 핵심 사항 중 하나는 재귀입니다. 또한 나누기와 정복을 사용한 철저한 검색 방법으로 간주됩니다. 역 추적 알고리즘은 첫 번째 하위 문제에 대한 솔루션이 더 이상 없으면 종료됩니다.
역 추적은 비결정론의 구현을 달성하는 데 도움이되는 알고리즘입니다. 주어진 이슈 공간에 대한 깊이 우선 검색이 필요합니다. 주로 Prolog와 같은 논리 프로그래밍 언어에서 사용됩니다. 역 추적을 적용 할 수있는 모든 위치에서 단일 테스트로 다수의 후보를 제거하므로 무차별 대입 기술보다 빠릅니다.
