2
저는 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 발생하는 상태 공간 트리, 그 노드가 부분적으로 처음으로 튜플을 구축 표현한다 "가 무엇을 의미합니까
- 있습니다 "i" 알고리즘의 이전 동작에 의해 정의 된 좌표입니다. 이러한 튜플 (x1, x2, x3, .. xi)이 해결책이 아닌 경우 알고리즘은 Si + 1의 다음 요소 을 찾습니다. (x1, x2, x3 ... xi)의 값과 문제 제약 조건을 계산하여 튜플에 (i + 1) st 좌표로 추가합니다. " ?
구체적으로 말하자면 알고리즘에 의해 작성자의 의미는 Si + 1에서 다음 요소를 찾습니다.
위의 진술을 4 개의 여왕 문제로 친절하게 요청하십시오.
요소가 존재하지 않으면 xi의 다음 값을 고려하기위한 알고리즘 백 트랙이 있습니까? 이 문제를 4 개의 여왕 문제와 함께 설명해주십시오.
고마워요!