목적지로 가는 도중에 특정 노드로부터의 경로가 악의적일 가능성이 없다면 그 경로를 따르지 마십시오.
돌아가서 시도 횟수를 줄입니다. 이를 가지치기라고 하며 불필요한 부분의 가동을 줄이기 위함입니다.
깊이 우선 검색과 비교하여 깊이 우선 검색은 모든 경로를 추적하지만 반면
역추적을 통해 불필요한 경로를 조기에 차단하기 때문에 상대적으로 경우의 수가 줄어듭니다.
그러나 N!의 경우에 대한 문제는 여전히 최악의 지수 시간을 필요로 합니다.
편집이 불가능하기 때문에 컷을 잘 하느냐에 따라 효율이 좌우됩니다.
쉽게 말해 특정 조건에 맞는 경우만 고려하고 그렇지 않은 경우 과감히 버린다는 뜻이다.
다양한 검색에 조건을 적용하고 다음과 같은 계산을 수행하여 이를 수행합니다. B. 답을 유추하기 어려운 상황으로 과감히 복귀한다.
검색 시간을 줄이기 위해 자주 사용됩니다.
백트래킹 기법의 기본은 다음과 같다.
특정 노드의 Promise를 확인한 후 Promise가 아닌 것으로 확인되면 해당 노드의 부모 노드가 됩니다.
다음 하위 노드로 역추적하십시오.
즉, 특정 노드를 방문했을 때 해당 노드가 솔루션으로 이동할 수 있으면 길조이고 그렇지 않으면 길조입니다.
그것은 유망하지 않습니다. 이 절망적인 매듭으로 가는 길을 고려하지 않는 것은 가지치기입니다.
전형적인 문제는 N-Queen 문제입니다.
역추적 알고리즘의 다음 절차를 적용하여 해결해 보자.
– 상태 공간 트리에서 깊이 우선 탐색
– 각 노드가 유망한지 확인
– 유망하지 않은 경우 돌아가서 탐색
나는 이해했다.