백트래킹 예제

나는 이동 언어와 Gotk3 프로젝트 (GTK3 라이브러리에 바인딩)를 선택하여 입력 퍼즐을 부여하는 간단한 GUI 응용 프로그램을 작성하여 가능한 모든 솔루션을 찾기 위해 역추적을 사용합니다. 역추적의 사용의 고전적인 교과서 예는 여덟 여왕 퍼즐입니다, 그 어떤 여왕이 다른 공격하지 않도록 표준 체스 판에 여덟 체스 여왕의 모든 배열을 요청합니다. 일반적인 역추적 접근 방식에서 부분 후보는 보드의 첫 번째 k 행에 있는 k 퀸의 배열이며 모두 다른 행과 열로 표시됩니다. 상호 공격하는 두 개의 여왕이 포함된 부분 솔루션은 포기할 수 있습니다. 이 문제 클래스의 경우 인스턴스 데이터 P는 정수 m과 n, 조건자 F입니다. 이 문제에 대한 일반적인 역추적 솔루션에서 부분 후보를 첫 번째 k 변수 x[1], x[2]에 할당할 0과 n 사이의 k에 대해 정수 c = (c[1], c[2], …, c[k]의 목록으로 정의할 수 있습니다. , x[k]. 그런 다음 루트 후보가 빈 목록()이 됩니다. 첫 번째 및 다음 절차는 역추적 알고리즘이 원칙적으로 주어진 문제에 대한 가능한 모든 솔루션을 제공하기 위해 다양한 방법으로 완료 될 수있는 부분 후보 집합을 여과합니다. 완료는 후보 확장 단계의 순서에 의해 점진적으로 수행됩니다. 이미 역추적을 사용했으면 매우 간단한 정의이지만, 처음 읽을 때 (또는 적어도 – 나에게는 아니었다) 명확하지 않다는 것을 깨닫습니다. 당신이 당신의 앞에 세 개의 상자가 있고 그들 중 하나만 금화를 가지고 있지만 어느 것을 모르는 상황을 고려하십시오.

그래서, 동전을 얻기 위해, 당신은 하나 씩 모든 상자를 열해야합니다. 먼저 첫 번째 상자를 선택합니다, 그것은 동전을 포함하지 않는 경우, 당신은 그것을 닫고 동전을 찾을 때까지 등등 두 번째 상자를 선택해야합니다. 이것이 역추적이 가장 좋은 해결책에 도달하기 위해 모든 하위 문제를 하나씩 해결하는 것입니다. 역추적을 사용하여 퍼즐이나 문제를 해결하는 데 사용할 수 있는 예는 다음과 같습니다.