역추적

Backtracking
제약 없는 최적화에 사용되는 라인 검색 알고리즘은 라인 검색 역추적을 참조하십시오.
그래프와 트리
검색 알고리즘
최단 경로
리스트
관련 토픽

역추적(backtracking)은 일부 계산 문제, 특히 제약 만족 문제에 대한 해결책을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 유효한 솔루션에 [1]대해 완료할 수 없다고 판단되면 후보("백트랙")를 포기합니다.

역추적 사용의 고전적인 예시는 8개의 여왕 퍼즐로, 여왕이 다른 여왕을 공격하지 않도록 표준 체스판에 8개의 체스 여왕의 모든 배치를 요구한다.공통 역추적 접근법에서 부분 후보자는 이사회의 첫 번째 k개 행에 k개의 퀸을 배치하고, 모두 다른 행과 열에 배치한다.서로 공격하는 2개의 퀸이 포함된 부분 솔루션은 폐기할 수 있습니다.

백트래킹은 "부분 후보 솔루션"의 개념을 인정하는 문제 및 유효한 솔루션에 대해 완료될 수 있는지 여부를 비교적 빠르게 테스트하는 문제에 대해서만 적용할 수 있습니다.예를 들어 순서가 매겨지지 않은 테이블에서 특정 값을 찾는 경우에는 사용할 수 없습니다.단, 적용 가능한 경우 백트래킹은 한 번의 테스트로 많은 후보를 제거할 수 있기 때문에 모든 후보를 강제로 열거하는 것보다 훨씬 빠릅니다.

역추적은 크로스워드, 구두산수, 스도쿠, 기타 많은 퍼즐과 같은 제약 만족 [2]문제를 해결하기 위한 중요한 도구입니다.이것은 종종 배낭 문제 및 기타 조합 최적화 문제에 대한 [3]해석에 가장 편리한 기술입니다.이것은 또한 Icon, Planner, Prolog와 같은 소위 논리 프로그래밍 언어의 기초이기도 합니다.

백트래킹은 사용자가 지정한 "블랙박스 절차"에 따라 달라집니다.이 절차에서는 해결해야 할 문제, 부분 후보의 특성 및 완전한 후보로 확장되는 방법을 정의합니다.따라서 이것은 특정 알고리즘이 아니라 메타 휴리스틱입니다.다만, 다른 많은 메타 휴리스틱과는 달리, 한정된 시간 내에 유한한 문제에 대한 모든 해결책을 찾을 수 있습니다.

"백트랙"이라는 용어는 미국의 수학자 D에 의해 만들어졌다. 1950년대의 H. 레머.[4]선구적인 문자열 처리 언어 SNOBOL(1962)은 내장형 일반 역추적 기능을 최초로 제공했을 가능성이 있습니다.

방법에 대한 설명

역추적 알고리즘은 주어진 문제에 대해 가능한 모든 해결책을 제공하기 위해 원칙적으로 다양한 방법으로 완성될 수 있는 일련의 부분 후보들을 열거합니다.완료는 일련의 후보 확장 단계에 따라 점진적으로 수행됩니다.

개념적으로, 부분 후보는 트리 구조의 노드, 즉 잠재적 검색 트리로 표현된다.각 부분 후보는 단일 확장 단계별로 다른 후보의 부모입니다. 트리의 잎은 더 이상 확장할 수 없는 부분 후보입니다.

역추적 알고리즘은 이 검색 트리를 루트에서 아래로 깊이 우선 순서로 재귀적으로 통과합니다.각 노드 c에서 알고리즘은 c가 유효한 해로 완성될 수 있는지 여부를 체크한다.사용할 수 없는 경우 c에 루트된 서브트리 전체가 건너뜁니다(프루닝 됩니다.그 이외의 경우 알고리즘 (1)은 c 자체가 유효한 솔루션인지 여부를 확인하고, 유효한 솔루션일 경우 사용자에게 보고하며, (2) c의 모든 서브트리를 재귀적으로 열거합니다.2개의 테스트와 각 노드의 자녀는 사용자가 지정한 절차에 따라 정의됩니다.

따라서 알고리즘이 통과하는 실제 검색 트리는 잠재적인 트리의 일부일 뿐입니다.알고리즘의 총 비용은 실제 트리의 노드 수에 각 노드의 취득 및 처리 비용을 곱한 값입니다.잠재적 검색 트리를 선택하고 플루닝 테스트를 구현할 때 이 사실을 고려해야 합니다.

유사 코드

특정 종류의 문제에 백트래킹을 적용하려면 해결할 문제의 특정 인스턴스에 대한 데이터 P와 6가지 절차 파라미터(root, reject, accept, first, next 및 출력)를 제공해야 합니다.이러한 절차에서는 인스턴스 데이터 P를 파라미터로 하여 다음 작업을 수행해야 합니다.

  1. root(P): 검색 트리의 루트에 부분 후보를 반환합니다.
  2. reject(P,c): 부분 후보 c가 완료할 가치가 없는 경우에만 true를 반환합니다.
  3. accept(P,c):c가 P의 솔루션이면 true를 반환하고 그렇지 않으면 false를 반환합니다.
  4. first(P,c): 후보 c의 첫 번째 확장을 생성합니다.
  5. next(P,s): 후보자의 내선번호 뒤에 다음 내선번호를 생성합니다.
  6. output(P,c): 용도에 따라 P의 솔루션 c를 사용합니다.

백트랙 알고리즘은 문제를 콜백트랙(root(P))으로 줄입니다.백트랙은 다음 재귀 절차입니다.

절차 역추적(c)은 거부(P, c)인 경우 반환하고, 수락(P, c)인 경우 출력(P, c)의 ← first(P, c)인 반면, s do NULL은 역추적(s)의 ← next(P, s)이다.

사용상의 고려 사항

reject 프로시저는 c의 확장이 P에 유효한 솔루션이 아닌 것이 확실한 경우에만 true를 반환하는 부울값 함수여야 합니다.절차가 명확한 결론에 도달할 수 없는 경우 false를 반환해야 합니다.잘못된 참 결과가 나오면 백트랙 절차에서 유효한 해결 방법을 찾을 수 없습니다.이 절차에서는 reject(P,t)가 검색 트리의 모든 상위 t에 대해 false를 반환했다고 가정할 수 있습니다.

한편, 백트래킹알고리즘의 효율성은 루트에 가능한 한 가까운 후보자에 대해 reject가 true를 반환하는 것에 의존합니다.reject가 항상 false를 반환하는 경우 알고리즘은 여전히 모든 솔루션을 찾지만 이는 brute-force 검색과 동일합니다.

c가 문제 인스턴스 P의 완전하고 유효한 솔루션인 경우 accept 절차는 true를 반환하고 그렇지 않은 경우 false를 반환해야 합니다.부분 후보 c와 트리 내의 모든 상위 후보가 거부 테스트를 통과했다고 가정할 수 있습니다.

위의 일반적인 유사 코드는 유효한 솔루션이 항상 잠재적 검색 트리의 잎이라고 가정하지 않습니다.즉, P에 대한 유효한 용액이 다른 유효한 용액을 산출하기 위해 더욱 확장될 가능성을 인정한다.

첫 번째 절차와 다음 절차는 트리의 노드 c의 자식, 즉 단일 확장 단계에 따라 c와 다른 후보를 열거하기 위해 백트래킹알고리즘에 의해 사용됩니다.콜의 첫 번째(P,c)는 어떤 순서로 c의 첫 번째 아이를 낳고, 다음 콜(P,s)은 그 순서로 노드의 다음 형제자매를 반환합니다.요청된 하위 항목이 없는 경우 두 함수 모두 고유한 "NULL" 후보를 반환해야 합니다.

루트, 첫 번째 및 다음 함수는 함께 부분 후보 집합과 잠재적 검색 트리를 정의합니다.P의 모든 솔루션이 트리 내 어딘가에서 발생하고 부분 후보가 두 번 이상 발생하지 않도록 선택해야 합니다.게다가 그들은 효율적이고 효과적인 거부 술어를 인정해야 한다.

얼리 스톱 바리안트

위의 의사 코드는 특정 인스턴스 P에 대한 솔루션인 모든 후보의 출력을 호출합니다.알고리즘은 첫 번째 솔루션 또는 지정된 수의 솔루션을 찾은 후 또는 지정된 수의 부분 후보를 테스트한 후 또는 CPU 시간을 소비한 후 중지하도록 변경할 수 있습니다.

예

역추적으로 해결된 스도쿠입니다.

퍼즐 또는 문제를 해결하기 위해 역추적을 사용할 수 있는 예는 다음과 같습니다.

다음으로 제약조건 만족 문제에 대해 백트래킹을 사용하는 예를 나타냅니다.

제약 만족도

일반적인 제약 조건 만족 문제는 임의의 제약 조건(예측 함수) F를 만족하는 정수 x = (x[1], x[2], …, x[n])의 리스트를 찾는 것으로 구성됩니다.

이 유형의 문제에 대해 인스턴스 데이터 P는 정수 m과 n, 그리고 술어 F가 됩니다.이 문제에 대한 전형적인 역추적 솔루션에서는 첫 번째 k 변수 x[1], x[2], …, x[k]에 할당되는 0과 n 사이의 임의의 k에 대해 부분 후보를 정수 c = (c[1], c[2], …, c[k])의 목록으로 정의할 수 있습니다.루트 후보는 빈 리스트()가 됩니다.첫 번째 절차와 다음 절차는 다음과 같습니다.

함수 first(P, c)는 k ← length(c)이며 k = n이면 NULL을 반환하고 그렇지 않으면 반환(c[1], c[2], …, c[k], 1)
함수 next(P, s)는 s[k] = m이면 k ← length(s)이고 NULL을 반환하지 않으면 null을 반환합니다(s[1], s[2], …, s[k - 1], 1 + s[k]).

여기서 length(c)는 목록 c의 요소 수입니다.

c의 k개의 요소로 시작하는n개의 정수 목록에서 제약조건 F가 충족되지 않으면 콜 거부(P, c)는 true를 반환해야 합니다.백트래킹을 유효하게 하기 위해서는 적어도 일부 후보 c에서는 이러한 모든n − k m-n-tuples를 열거하지 않고 이 상황을 검출할 수 있는 방법이 필요합니다.

예를 들어 F가 여러 부울 술어, F = F[1] f F[2] … ... f F[p]의 조합이고 각 F[i]가 변수 x[1], …, x[n]의 작은 부분 집합에만 의존하는 경우, 거부 절차는 x[1]에만 의존하는 항 F[i]를 간단히 확인할 수 있습니다.실제로 x[1], …, x[k - 1]에만 의존하는 용어는 검색 트리에서 테스트되므로 거부에서는 x[k]에 의존하는 용어만 체크해야 합니다.

위와 같이 reject가 구현되어 있다고 가정하면 accept(P, c)는 c가 완전한지, 즉 n개의 요소가 있는지 확인만 하면 됩니다.

일반적으로 가장 중요한 변수(즉, 값 옵션이 가장 적거나 후속 선택에 더 큰 영향을 미치는 변수)부터 시작하도록 변수 목록을 정렬하는 것이 좋습니다.

또한 다음 함수가 이미 할당된 변수 값을 기반으로 부분 후보를 확장할 때 할당해야 하는 변수를 선택할 수 있습니다.제약 전파 기술에 의해 한층 더 개선을 얻을 수 있다.

백업에 사용되는 최소한의 복구 값을 유지할 뿐만 아니라, 일반적으로 백트랙 구현에서는 값 변경 내역을 기록하기 위해 가변 추적을 유지합니다.효율적인 구현은 선택지가 없을 때 두 개의 연속된 변경 사이에 가변 추적 엔트리가 생성되지 않도록 합니다.백트래킹에서는 모든 변경이 단일 작업으로 지워지기 때문입니다.

변수 추적의 다른 방법은 변수에 마지막으로 변경이 이루어진 시점의 타임스탬프를 유지하는 것입니다.타임스탬프는 선택 포인트의 타임스탬프와 비교됩니다.선택 포인트의 관련 시간이 변수의 시간보다 늦은 경우 선택 포인트가 발생하기 전에 변경되었기 때문에 선택 포인트가 역추적될 때 변수를 되돌릴 필요가 없습니다.

「 」를 참조해 주세요.

메모들

  1. ^ 스도쿠 해결 알고리즘을 참조하십시오.

레퍼런스

  1. ^ Gurari, Eitan (1999). "CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms". Archived from the original on 17 March 2007.
  2. ^ A. Biere; M. Heule; H. van Maaren (29 January 2009). Handbook of Satisfiability. IOS Press. ISBN 978-1-60750-376-7.
  3. ^ Des Watson (22 March 2017). A Practical Approach to Compiler Construction. Springer. ISBN 978-3-319-52789-5.
  4. ^ Rossi, Francesca; Beek, Peter Van; Walsh, Toby (August 2006). "Constraint Satisfaction: An Emerging Paradigm". Handbook of Constraint Programming. Amsterdam: Elsevier. p. 14. ISBN 978-0-444-52726-4. Retrieved 2008-12-30.

추가 정보

외부 링크