백 트래킹 디자인 기술의 일반적인 정의

Question

저는 Anany Levtin의 알고리즘 설계 및 분석 소개에서 추적 알고리즘 설계 기법을 다시 읽습니다.

나는 역 추적 알고리즘의 일반적인 정의를 이해하는 데 어려움을 겪고 있으며 4 개의 여왕 문제에 매핑합니다. 보다 일반적인 관점에서 알고리즘 설계 기법을 역 추적 용

대부분 되돌아 알고리즘 다음 설명 를 장착한다.

되돌아 알고리즘의 출력은 N 튜플로 생각할 수 (X1, X2, X3, ..., XN) 각각 XI 일부 유한 직선 순서화 된 세트의 Si 원소 좌표 여기서. 예를 들어, n-queens 문제의 경우 각 Si는 1 - n의 정수입니다. 튜플은 몇 가지 추가 제약 조건 (예 : n-queens 문제의 요구 사항 인 )을 충족해야 할 수도 있습니다. 각 Si를 {1, 2, 3, 4}

백 트래킹 알고리즘은 명시 적으로 또는 implicityly 생성하는 상태 공간 트리의 노드가 부분적으로 생성 된 표현한다 튜플 세트 4 퀸 문제에 대해, 예를 들어

알고리즘의 이전 동작으로 정의 된 첫 번째 "i"좌표와 함께. 그러한 튜플 (x1, x2, x3, .. xi)이 해가 아닌 경우, 알고리즘은 (x1, x2, x3 ... xi)의 값과 일치하는 Si + 1의 다음 요소를 찾습니다. 문제 제약 조건을 추가하고 튜플에 (i + 1) st 좌표로 을 추가합니다. 그러한 요소에 이없는 경우 알고리즘은 xi의 다음 값과 등을 고려하여 역 추적합니다. 위의 텍스트에

내 질문 작성자가 다시 추적 알고리즘은 명시 적으로 또는 implicityly 발생하는 상태 공간 트리, 그 노드가 부분적으로 처음으로 튜플을 구축 표현한다 "가 무엇을 의미합니까

1. 있습니다 "i" 알고리즘의 이전 동작에 의해 정의 된 좌표입니다. 이러한 튜플 (x1, x2, x3, .. xi)이 해결책이 아닌 경우 알고리즘은 Si + 1의 다음 요소 을 찾습니다. (x1, x2, x3 ... xi)의 값과 문제 제약 조건을 계산하여 튜플에 (i + 1) st 좌표로 추가합니다. " ?

   구체적으로 말하자면 알고리즘에 의해 작성자의 의미는 Si + 1에서 다음 요소를 찾습니다.

   위의 진술을 4 개의 여왕 문제로 친절하게 요청하십시오.

2. 요소가 존재하지 않으면 xi의 다음 값을 고려하기위한 알고리즘 백 트랙이 있습니까? 이 문제를 4 개의 여왕 문제와 함께 설명해주십시오.

고마워요!

Answer 1

이 백 트랙킹에 대한 설명은 특정 용도로 사용되거나 증명되지 않는 정식 표기법을 많이 사용하기 때문에 실제로 따라하기가 어렵습니다.덜 숙고 된 4-queens 문제를 예로 들어 설명해 보겠습니다.

역 추적 과정이 시작될 때 보드가 비어 있습니다. 이것이 상태 공간 트리의 근원입니다. 이 루트에는 자식 노드가 있습니다. 첫 번째 여왕을 넣을 수있는 각각의 노드에 하나씩 있습니다. 다음 단계로 넘어 가기 전에 (즉, 상태 공간 트리의 BFS가 될) 각 자식 노드를 구성하는 대신 첫 번째 여왕에 대해 가능한 한 위치를 선택하여 하나의 자식 노드를 만듭니다. 이 자식 노드에서 두 번째 여왕을 배치 할 여러 옵션이 다시 있으므로 하나를 선택하는 등의 작업을 수행 할 수 있습니다.

남아있는 여왕을 넣을 가능성이없는 노드에 도착하면 우리는 다시 궤도에 진입합니다. 우리는 그 노드의 아버지 노드로 한 단계 올라가서 우리가 아직 탐험하지 않은 가능성이 있는지 확인합니다. 만약 그렇다면 각각의 자식 노드를 생성하여 탐색합니다. 다시 돌아 오지 않으면 다른 레벨로 올라갑니다. 문제에 대한 해결책을 찾거나 (모든 여왕이 배치됩니다) 루트 노드의 모든 하위 노드를 확장하고 도착했습니다. 백 트랙 작업 중 루트 노드 - 솔루션이 없음을 의미합니다.