backtracking 알고리즘 예제

따라서 알고리즘에 의해 트래버스되는 실제 검색 트리는 잠재적 트리의 일부일 뿐입니다. 알고리즘의 총 비용은 실제 트리의 노드 수와 각 노드를 가져오고 처리하는 데 드는 비용입니다. 이 사실은 잠재적인 검색 트리를 선택하고 가지 치기 테스트를 구현할 때 고려해야 합니다. 먼저 지금 검사중인 조각을 그리드에 배치한 다음 모든 빈 영역의 크기를 계산합니다(알고리즘과 같은 플러드 채우기 사용). 함수의 끝에서 최소 빈 영역이 더 작은 나머지 부분보다 작은 경우 반환합니다. 따라서 이 함수가 true를 반환하면 이 계산 분기가 솔루션에 도달하지 않으므로 잘라낼 수 있습니다. 우리가 한 일은 솔루션에 도착하지 않을 분기를 따르지 않도록 몇 가지 추가 계산 (최소 빈 공간 크기를 찾기 위해)을 추가하는 것입니다. 일반적으로 알고리즘의 일반적인 성능을 악화시키는 것이 될 수 있기 때문에 추가 계산을 추가하는 것이 타리인지 아닌지 해결하려는 문제에 따라 달라집니다. 위의 의사 코드는 지정된 인스턴스 P에 대한 솔루션인 모든 후보에 대한 출력을 호출합니다. 알고리즘은 첫 번째 솔루션 또는 지정된 수의 솔루션을 찾은 후 중지하도록 수정할 수 있습니다. 또는 지정된 수의 부분 후보를 테스트한 후 또는 지정된 양의 CPU 시간을 소비한 후에.

나는 이동 언어와 Gotk3 프로젝트 (GTK3 라이브러리에 바인딩)를 선택하여 입력 퍼즐을 부여하는 간단한 GUI 응용 프로그램을 작성하여 가능한 모든 솔루션을 찾기 위해 역추적을 사용합니다. 백업에 사용되는 최소한의 복구 값을 유지하는 것 외에도 역추적 구현은 일반적으로 가변 추적을 유지하여 값 변경 기록을 기록합니다. 백트래킹은 모든 변경 내용을 단일 작업으로 지우므로 선택 지점이 없는 경우 두 개의 연속변경 간에 변수 추적 항목을 만들지 않습니다. 일반적으로 모든 제약 조건 만족도 문제는 모든 객관적인 솔루션에 명확하고 잘 정의된 제약 조건이 있으며, 이는 솔루션에 대한 후보를 점진적으로 구축하고 후보자를 포기하는 즉시 후보자를 결정합니다(“역추적”). 백트래킹을 통해 해결할 수 있습니다. 그러나 논의되는 대부분의 문제는 동적 프로그래밍 또는 욕심 알고리즘과 같은 다른 알려진 알고리즘을 사용하여 입력 크기 순으로 로그, 선형, 선형 로그 시간 복잡성을 해결할 수 있으므로 역추적 알고리즘은 일반적으로 시간과 공간 모두에서 기하급수적이기 때문에 모든 면에서 역추적 알고리즘을 추적합니다.