역 추적 알고리즘은 원칙적으로 주어진 문제에 대한 모든 가능한 해결책을 제공하기 위해 다양한 방법으로 완료 될 수있는 부분 후보 세트를 열거합니다. 완성은 후보 확장 단계 시퀀스에 의해 점진적으로 수행됩니다.
개념적으로 부분 후보는 트리 구조,잠재적 검색 트리의 노드로 표시됩니다. 각 부분 후보자는 단일 확장 단계에 의해 다른 후보자의 부모입니다; 나무의 잎은 더 이상 확장 할 수없는 부분 후보입니다.
역추적 알고리즘은 이 검색 트리를 깊이 우선 순서로 루트에서 재귀적으로 순회합니다. 각 노드에서 씨,알고리즘은 씨 유효한 솔루션을 완료 할 수 있는지 여부를 확인합니다. 그럴 수 없다면 씨에 뿌리를 둔 전체 하위 트리를 건너 뜁니다(정리). 두 테스트 및 각 노드의 자식 사용자 지정 프로시저에 의해 정의 됩니다.
따라서 알고리즘에 의해 탐색되는 실제 검색 트리는 잠재적 트리의 일부일뿐입니다. 알고리즘의 총 비용은 실제 트리의 노드 수와 각 노드를 획득하고 처리하는 비용을 곱한 값입니다. 이 사실은 잠재적 인 검색 트리를 선택하고 가지 치기 테스트를 구현할 때 고려해야합니다.
의사 코드 편집
특정 문제 클래스에 역 추적을 적용하려면 해결해야 할 문제의 특정 인스턴스에 대한 데이터 피와 6 개의 절차 매개 변수 인 루트,거부,수락,첫 번째,다음 및 출력을 제공해야합니다. 이러한 절차에서는 인스턴스 데이터를 매개 변수로 사용하고 다음을 수행해야 합니다:
- 루트(피):검색 트리의 루트에서 부분 후보를 반환.
- 거부(피,기음):부분 후보 씨가 완료 할 가치가없는 경우에만 참 반환.
- 수락(피,기음): 반환 참 씨 의 솔루션 피,그리고 거짓 그렇지 않으면.
- 다음(피,에스):확장 후 후보의 다음 대체 확장을 생성 에스.
- 출력(피,씨):솔루션을 사용 씨 의 피,응용 프로그램에 적절한.여기서 역추적은 다음과 같은 재귀 프로시저입니다:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
사용 고려편집
거부 프로시저는 가능한 확장이 없는 경우에만 참 반환하는 부울 값 함수여야 합니다. 잘못된 실제 결과로 인해 비티 프로시저가 일부 유효한 솔루션을 놓칠 수 있습니다. 이 절차는 거부(피,티)가 모든 조상에 대해 거짓으로 반환되었다고 가정 할 수 있습니다.
한편,역추적 알고리즘의 효율성은 가능한 한 루트에 가까운 후보에 대한 리젝트 리턴 트룸에 의존한다. 거부가 항상 거짓을 반환하는 경우 알고리즘은 여전히 모든 솔루션을 찾을 수 있지만 무차별 대입 검색과 동일합니다.
수락 프로시저는 문제 인스턴스에 대한 완전하고 유효한 솔루션인 경우 참 반환해야 합니다. 부분 후보 씨와 트리의 모든 조상이 거부 테스트를 통과했다고 가정 할 수 있습니다.
위의 일반 의사 코드는 유효한 솔루션이 항상 잠재적 검색 트리의 잎이라고 가정하지 않습니다. 다른 말로,그것은 가능성을 인정 유효한 솔루션 에 대한 피 다른 유효한 솔루션을 산출하기 위해 더 확장 될 수 있습니다.
첫 번째 및 다음 프로시저는 역추적 알고리즘에서 노드의 자식을 열거하는 데 사용됩니다. 첫 번째 호출(피,씨)의 첫 번째 자식을 산출해야합니다 씨,어떤 순서로; 그리고 다음 호출(피,에스)은 노드의 다음 형제를 반환해야합니다 에스,순서대로. 요청 된 자식이 존재하지 않는 경우 두 함수 모두 고유 한”널”후보를 반환해야합니다.
함께 루트,첫 번째 및 다음 함수는 부분 후보 집합과 잠재적 검색 트리를 정의합니다. 모든 솔루션이 트리 어딘가에서 발생하고 부분 후보가 두 번 이상 발생하지 않도록 선택해야합니다. 또한,그들은 효율적이고 효과적인 거부 술어를 인정해야합니다.
초기 중지 변수편집
위의 의사 코드는 주어진 인스턴스에 대한 해결책 인 모든 후보에 대한 출력을 호출합니다.