[algorithm] 역 추적과 깊이 우선 검색의 차이점은 무엇입니까?
역 추적과 깊이 우선 검색의 차이점은 무엇입니까?
답변
역 추적 은보다 일반적인 목적의 알고리즘입니다.
깊이 우선 검색 은 트리 구조 검색과 관련된 특정 형태의 역 추적입니다. Wikipedia에서 :
하나는 루트에서 시작하여 (그래프 케이스에서 일부 노드를 루트로 선택) 역 추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색합니다.
역 추적을 트리 작업 수단의 일부로 사용하지만 트리 구조로 제한됩니다.
그러나 역 추적은 논리적 트리인지 여부에 관계없이 도메인의 일부를 제거 할 수있는 모든 유형의 구조에서 사용할 수 있습니다. Wiki 예제는 체스 판과 특정 문제를 사용합니다. 특정 동작을보고 제거한 다음 가능한 다음 동작으로 되돌아가 제거 할 수 있습니다.
답변
다른 관련 질문에 대한 답변이 더 많은 통찰력을 제공 한다고 생각 합니다 .
나에게 역 추적과 DFS의 차이점은 역 추적은 암시 적 트리를 처리하고 DFS는 명시 적 트리를 처리한다는 것입니다. 이것은 사소한 것처럼 보이지만 많은 것을 의미합니다. 역 추적을 통해 문제의 검색 공간을 방문하면 묵시적 트리가 탐색되고 그 중간에서 정리됩니다. 그러나 DFS의 경우 처리하는 트리 / 그래프는 명시 적으로 구성되어 있으며 허용되지 않는 경우는 검색이 완료되기 전에 이미 버려졌습니다.
따라서 역 추적은 암시 적 트리의 경우 DFS이고 DFS는 가지 치기없이 역 추적합니다.
답변
역 추적은 일반적으로 DFS와 검색 정리로 구현됩니다. 길을 따라 부분 솔루션을 구성하는 검색 공간 트리 깊이를 탐색합니다. 무차별 대입 DFS는 실제로 의미가없는 모든 검색 결과를 구성 할 수 있습니다. 이것은 또한 모든 솔루션 (n! 또는 2 ^ n)을 구성하는 데 매우 비효율적 일 수 있습니다. 따라서 실제로 DFS를 수행하는 것처럼 실제 작업의 맥락에서 말이되지 않는 부분 솔루션도 제거하고 유효한 최적 솔루션으로 이어질 수있는 부분 솔루션에 집중해야합니다. 이것이 실제 역 추적 기법입니다. 가능한 한 빨리 부분 솔루션을 버리고 한 발 뒤로 물러나서 로컬 최적을 다시 찾으려고합니다.
BFS를 사용하여 검색 공간 트리를 탐색하고 그 과정에서 역 추적 전략을 실행하는 것을 멈추지 않지만 실제로는 검색 상태를 대기열에 레이어별로 저장해야하고 트리 너비가 높이까지 기하 급수적으로 증가하기 때문에 실제로는 의미가 없습니다. 그래서 우리는 매우 빠르게 많은 공간을 낭비 할 것입니다. 이것이 나무가 일반적으로 DFS를 사용하여 횡단하는 이유입니다. 이 경우 검색 상태는 스택 (호출 스택 또는 명시 적 구조)에 저장되며 트리 높이를 초과 할 수 없습니다.
답변
일반적으로 깊이 우선 검색은 값을 찾기 위해 실제 그래프 / 트리 구조를 반복하는 방법 인 반면 역 추적은 솔루션을 찾기 위해 문제 공간을 반복하는 방법입니다. 역 추적은 나무와 반드시 관련이있는 것은 아닌보다 일반적인 알고리즘입니다.
답변
DFS는 특별한 형태의 역 추적입니다. 역 추적은 DFS의 일반적인 형태입니다.
DFS를 일반적인 문제로 확장하면 역 추적이라고 부를 수 있습니다. 역 추적을 사용하여 트리 / 그래프 관련 문제를 해결하면 DFS라고 부를 수 있습니다.
그들은 알고리즘 측면에서 동일한 아이디어를 가지고 있습니다.
답변
Donald Knuth에 따르면 동일합니다. 다음은 N-queens 및 Sudoku 솔버와 같은 “나무가 아닌”문제를 해결하는 데 사용되는 Dancing Links 알고리즘에 대한 그의 논문의 링크입니다.
답변
IMHO, 대부분의 답변은 대체로 부정확하거나 확인할 참조가 없습니다. 그래서 참조와 함께 매우 명확한 설명을 공유하겠습니다 .
첫째, DFS는 일반적인 그래프 순회 (및 검색) 알고리즘입니다. 따라서 모든 그래프 (또는 포리스트)에 적용 할 수 있습니다. 트리는 특별한 종류의 그래프이므로 DFS는 트리에서도 작동합니다. 본질적으로, 그것이 나무 나 그와 비슷한 것에 만 효과가 있다고 말하지 말자.
[1]에 따르면 Backtracking은 주로 공간 (메모리) 절약에 사용되는 특별한 종류의 DFS입니다. 이러한 종류의 그래프 알고리즘에서는 인접 목록 표현을 사용 하고 노드의 모든 인접 이웃 ( 트리의 경우 직계 자식 ) 을 방문하기 위해 반복 패턴을 사용하는 데 익숙하기 때문에 제가 언급하려는 구분은 혼란스러워 보일 수 있습니다. , 우리는 종종 get_all_immediate_neighbors 의 잘못된 구현 이 기본 알고리즘의 메모리 사용에 차이를 일으킬 수 있음을 무시합니다 .
또한 그래프 노드에 분기 계수 b와 지름 h ( 나무의 경우 트리 높이 )가있는 경우 노드를 방문하는 각 단계에서 모든 인접 이웃을 저장하면 메모리 요구 사항은 big-O (bh) 입니다. 그러나 한 번에 하나의 (즉시) 이웃 만 가져와 확장하면 메모리 복잡성이 big-O (h)로 줄어 듭니다 . 전자의 구현 유형을 DFS 라고 하고 후자 의 구현을 역 추적 이라고 합니다.
이제 고급 언어로 작업하는 경우 실제로 DFS를 가장하여 역 추적을 사용하고있을 가능성이 높습니다. 더욱이, 매우 큰 문제 세트에 대해 방문한 노드를 추적하는 것은 실제로 메모리 집약적 일 수 있습니다. get_all_immediate_neighbors (또는 무한 루프에 들어 가지 않고 노드 재 방문을 처리 할 수있는 알고리즘) 의 신중한 설계를 요구합니다 .
[1] Stuart Russell 및 Peter Norvig, 인공 지능 : 현대적인 접근 방식, 3rd Ed
