역추적 소개

역추적 알고리즘을 기반으로 문제를 해결하는 기술입니다. 재귀 호출을 사용하여 시간이 지남에 따라 값을 단계적으로 증가시키면서 솔루션을 빌드하여 솔루션을 찾습니다. 문제 해결을 위해 주어진 제약 조건을 기반으로 문제 해결을 일으키지 않는 솔루션을 제거합니다.

역추적 알고리즘은 일부 특정 유형의 문제에 적용됩니다.

• 문제의 실행 가능한 솔루션을 찾는 데 사용되는 결정 문제입니다.

• 적용할 수 있는 최상의 솔루션을 찾는 데 사용되는 최적화 문제입니다.

• 문제의 가능한 모든 솔루션 세트를 찾는 데 사용되는 열거형 문제입니다.

역추적 문제에서 알고리즘은 문제에 대해 실행 가능한 솔루션이 발견되지 않는 경우 문제가 역추적할 수 있는 몇 가지 작은 체크포인트가 있는 솔루션에 대한 시퀀스 경로를 찾으려고 시도합니다.

예,

여기,

녹색은 시작점, 파란색은 중간점, 빨간색은 실현 가능한 솔루션이 없는 포인트, 짙은 녹색은 끝 솔루션입니다.

여기에서 알고리즘이 솔루션인지 여부를 확인하기 위해 끝까지 전파할 때 솔루션이면 솔루션을 반환하고 그렇지 않으면 솔루션을 찾기 위해 다음 지점으로 트랙을 찾기 위해 한 단계 뒤에 있는 지점으로 역추적합니다.

알고리즘

Step 1 - current_position이 목표이면 성공을 반환Step 2 - else,Step 3 - current_position이 끝점이면 실패를 반환합니다.Step 4 - 그렇지 않으면 current_position이 끝점이 아닌 경우 위의 단계를 탐색하고 반복합니다. 

 이 역추적 문제를 사용하여 N-퀸 문제에 대한 해결책을 찾아봅시다. .
 

 N-Queen 문제에서는 NxN 체스판이 주어지고 두 개의 퀸이 서로 공격하지 않도록 보드에 n개의 퀸을 놓아야 합니다. 퀸이 가로, 세로 또는 대각선 지점에 있는 경우 다른 퀸을 공격합니다. 여기서는 4-Queen problem을 해보겠습니다.
 

 여기에서 솔루션은 -
 

 
 

 여기에 위치에 대한 퀸이 1인 n개의 퀸 문제에 대한 이진 출력이 배치됩니다.
 
{0, 1, 0, 0}{0, 0, 0, 1}{1, 0, 0, 0}{0, 0, 1, 0}
 

 n개의 퀸 문제를 풀기 위해 퀸을 한 행의 다른 위치에 배치하려고 합니다. 그리고 다른 퀸과 충돌 여부를 확인합니다. 서로를 공격하는 두 개의 여왕이 있는 경우 현재 여왕의 위치입니다. 그들이 공격하는 경우 여왕의 이전 위치로 되돌아가 위치를 변경합니다. 그리고 퀸의 크래쉬를 다시 확인해보세요.
 
알고리즘
 
 

 1단계 - 배열의 첫 번째 위치에서 시작합니다.
 2단계 - 퀸을 보드에 놓고 확인합니다. Do, Step 2.1 - 퀸을 배치한 후 솔루션의 일부로 위치를 표시한 다음 이것이 솔루션으로 이어지는지 재귀적으로 확인합니다. 2.2단계 - 이제 퀸을 배치해도 솔루션 및 트랙백으로 이어지지 않으면 (a) 단계로 이동하여 퀸을 다른 행에 배치합니다. 2.3단계 - 퀸 배치가 리드를 솔루션으로 반환하는 경우 TRUE를 반환합니다. 3단계 - 모든 퀸이 배치되면 TRUE를 반환합니다. 

 4단계 - 모든 행을 시도했지만 해결책이 없으면 FALSE를 반환합니다.
 
 

 이제 역추적을 사용하여 Rat in Maze 문제를 해결해 보겠습니다. 문제 -
 

 미로 문제의 쥐에서 우리는 NxN 미로가 미로의 첫 번째 위치, 즉 [0][0]이고 배열의 [n-1][n-1] 위치에서 끝납니다. 이 경로에는 해결책으로 이어지지 않는 일부 죽은 길이 있습니다.
 

 이 문제에서 역추적을 사용하여 미로의 최종 목표 위치에 도달하기 위해 단계적으로 내려갑니다.
 
아래 2D 배열은 문제가 어떻게 보이는지 표시합니다.
 

 
 

 여기서 점선은 이동 경로를 나타냅니다.