백 트랙킹 알고리즘 학습

Question

백 트랙킹 알고리즘을 배우고 싶습니다. 누군가 내게 그것을 가르쳐 줄 수 있습니까? 나는 몇몇 웹 사이트에서 배우려고했으나 제대로 작동하지 않았다. 그래서 누군가 나를 가르쳐주십시오. 고맙습니다!

Answer 1

언어 불가지론자인 this 자습서가 좋지만 필요한 직관을 제공 할 수있는 몇 가지 예가 나와 있습니다.

다시 말하면 backtracking의 개념은 전혀 이해하기 어렵지 않습니다. 역 추적 알고리즘은 근본적으로 무차별 대입을 수행 할 때와 마찬가지로을 제외한 을 제외한 모든 솔루션 공간을 탐색하므로 가능한 한 실현되지 않아이라는 부분 솔루션 으로 역 추적합니다.

예

은 eight queens problem 잘 알려진 부분이 용액을 고려한다. 처음 네 열의

여왕은 이미 배치되어 있지만, 마지막 하나는 잘못된 광장에서입니다. brute force 솔루션은 열의 나머지 부분에 대해 여왕을 배치하면서이 부분적인 솔루션이 어떻게 보완 되더라도 그 결과는 무효가된다는 사실을 알지 못합니다.

백 트랙킹 알고리즘은 "더 똑똑합니다": 네 번째 여왕이 잘못 배치되어 다른 사각형을 고려하여 "돌아갈"수 있습니다.

Answer 2

Fundamentals Of Computer Algorithms에는 역 추적에 대한 유용한 장이 포함되어 있습니다. 그러나 공식적인 알고리즘 텍스트 및 데이터 구조에 얼마나 익숙한지를 지정하지 않았습니다. 복잡성 분석과 같은 기본적인 알고리즘에 익숙하지 않거나 나무가 무엇인지 모르는 경우이 책을 읽는 데 문제가있을 수 있습니다. 나는이 경우 처음부터 책을 읽을 필요가 있음을 의미합니다. 직접 건너 뛰기 장으로 직접 점프하면 큰 도움이되지 않습니다.