역 추적과 깊이 우선 검색의 차이점은 무엇입니까?
역 추적과 깊이 우선 검색의 차이점은 무엇입니까?
역 추적 은보다 일반적인 목적의 알고리즘입니다.
깊이 우선 검색 은 트리 구조 검색과 관련된 특정 형태의 역 추적입니다. Wikipedia에서 :
하나는 루트에서 시작하여 (그래프 케이스에서 일부 노드를 루트로 선택) 역 추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색합니다.
역 추적을 트리 작업 수단의 일부로 사용하지만 트리 구조로 제한됩니다.
그러나 역 추적은 논리적 트리인지 여부에 관계없이 도메인의 일부를 제거 할 수있는 모든 유형의 구조에서 사용할 수 있습니다. Wiki 예제는 체스 판과 특정 문제를 사용합니다. 특정 동작을보고 제거한 다음 가능한 다음 동작으로 되돌아 가서 제거 할 수 있습니다.
다른 관련 질문에 대한 답변이 더 많은 통찰력을 제공 한다고 생각 합니다 .
나에게 역 추적과 DFS의 차이점은 역 추적은 암시 적 트리를 처리하고 DFS는 명시 적 트리를 처리한다는 것입니다. 이것은 사소한 것처럼 보이지만 많은 것을 의미합니다. 역 추적을 통해 문제의 검색 공간을 방문하면 묵시적 트리가 탐색되고 그 중간에서 정리됩니다. 그러나 DFS의 경우 처리하는 트리 / 그래프는 명시 적으로 구성되어 있으며 허용되지 않는 경우는 검색이 완료되기 전에 이미 버려졌습니다.
따라서 역 추적은 암시 적 트리의 경우 DFS이고 DFS는 가지 치기없이 역 추적합니다.
일반적으로 깊이 우선 검색은 값을 찾기 위해 실제 그래프 / 트리 구조를 반복하는 방법 인 반면 역 추적은 솔루션을 찾기 위해 문제 공간을 반복하는 방법입니다. 역 추적은 나무와 반드시 관련이있는 것은 아닌보다 일반적인 알고리즘입니다.
DFS는 특별한 형태의 역 추적입니다. 역 추적은 DFS의 일반적인 형태입니다.
DFS를 일반적인 문제로 확장하면 역 추적이라고 부를 수 있습니다. 역 추적을 사용하여 트리 / 그래프 관련 문제를 해결하면 DFS라고 부를 수 있습니다.
그들은 알고리즘 측면에서 동일한 아이디어를 가지고 있습니다.
Donald Knuth에 따르면 동일합니다. 다음은 N-queens 및 Sudoku 솔버와 같은 "나무가 아닌"문제를 해결하는 데 사용되는 Dancing Links 알고리즘에 대한 그의 논문의 링크입니다.
깊이 우선은 트리를 탐색하거나 검색하는 알고리즘입니다. 를 참조하십시오 여기 . 역 추적은 솔루션 후보가 형성되고 나중에 이전 상태로 역 추적하여 폐기 될 때마다 사용되는 훨씬 더 광범위한 용어입니다. 를 참조하십시오 여기 . 깊이 우선 검색은 역 추적을 사용하여 분기를 먼저 검색하고 (솔루션 후보) 성공하지 못한 경우 다른 분기를 검색합니다.
역 추적은 일반적으로 DFS와 검색 정리로 구현됩니다. 길을 따라 부분 솔루션을 구성하는 검색 공간 트리 깊이를 탐색합니다. 무차별 대입 DFS는 실제로 의미가없는 모든 검색 결과를 구성 할 수 있습니다. 이것은 또한 모든 솔루션 (n! 또는 2 ^ n)을 구성하는 데 매우 비효율적 일 수 있습니다. 따라서 실제로 DFS를 수행하는 것처럼 실제 작업의 맥락에서 말이되지 않는 부분 솔루션도 잘라 내고 유효한 최적 솔루션으로 이어질 수있는 부분 솔루션에 집중해야합니다. 이것이 실제 역 추적 기법입니다. 가능한 한 빨리 부분 솔루션을 버리고 한 발 뒤로 물러나서 로컬 최적을 다시 찾으려고합니다.
BFS를 사용하여 검색 공간 트리를 탐색하고 그 과정에서 역 추적 전략을 실행하는 것을 멈추지 않지만 실제로는 검색 상태를 대기열에 계층별로 저장해야하고 트리 너비가 높이까지 기하 급수적으로 증가하기 때문에 실제로는 의미가 없습니다. 그래서 우리는 매우 빠르게 많은 공간을 낭비 할 것입니다. 이것이 나무가 일반적으로 DFS를 사용하여 횡단하는 이유입니다. 이 경우 검색 상태는 스택 (호출 스택 또는 명시 적 구조)에 저장되며 트리 높이를 초과 할 수 없습니다.
A의 깊이 우선 탐색 , 당신은 트리의 루트에서 시작하여 다음 각 분기를 따라 멀리 당신을 탐구 철수 이후의 각 부모 노드와 그것의 아이를 횡단
역 추적 은 목표의 끝에서 시작하여 점진적으로 뒤로 이동하여 점진적으로 솔루션을 구축하는 일반화 된 용어입니다.
IMO, 역 추적의 특정 노드에서 먼저 각 하위 노드로 깊이 분기하려고 시도하지만 하위 노드로 분기하기 전에 이전 하위 상태를 "삭제"해야합니다 (이 단계는 back과 동일합니다. 부모 노드로 이동). 즉, 각 형제 상태는 서로 영향을주지 않아야합니다.
반대로 일반 DFS 알고리즘에서는 일반적으로 이러한 제약이 없으며 다음 형제 노드를 구성하기 위해 이전 형제 상태를 지울 필요가 없습니다.
아이디어-어느 지점에서 시작하여 원하는 끝점인지 확인하고, 그렇다면 해결책이 다음 가능한 모든 위치로 이동하는 것을 발견하고 더 이상 갈 수없는 경우 이전 위치로 돌아가서 현재를 표시하는 다른 대안을 찾습니다. 길은 우리를 해결책으로 이끌지 않을 것입니다.
이제 역 추적과 DFS는 2 개의 다른 추상 데이터 유형에 적용된 동일한 아이디어에 주어진 2 개의 다른 이름입니다.
아이디어가 행렬 데이터 구조에 적용되면 역 추적이라고합니다.
동일한 아이디어가 트리 나 그래프에 적용되면 DFS라고합니다.
여기서 진부한 것은 행렬이 그래프로 변환 될 수 있고 그래프가 행렬로 변환 될 수 있다는 것입니다. 그래서 우리는 실제로 아이디어를 적용합니다. 그래프에서는 DFS라고하고 행렬에서는 역 추적이라고합니다.
두 알고리즘의 아이디어는 동일합니다.
DFS는 그래프를 탐색하거나 탐색하는 방법을 설명합니다. 그것은 주어진 선택을 가능한 한 깊게한다는 개념에 초점을 맞추고 있습니다.
역 추적은 일반적으로 DFS를 통해 구현되지만 가능한 한 빨리 타협하지 않는 검색 부분 공간을 정리하는 개념에 더 중점을 둡니다.
'Programing' 카테고리의 다른 글
| 파이썬에서 상속의 요점은 무엇입니까? (0) | 2020.10.08 |
|---|---|
| Winforms TableLayoutPanel 프로그래밍 방식으로 행 추가 (0) | 2020.10.08 |
| @Transactional 어노테이션을 어디에 넣어야합니까? 인터페이스 정의 또는 구현 클래스에서? (0) | 2020.10.08 |
| -webkit-transform은 무엇입니까 : translate3d (0,0,0); (0) | 2020.10.08 |
| redis가 이미 스택의 일부인 경우 Memcached가 Redis와 함께 계속 사용되는 이유는 무엇입니까? (0) | 2020.10.08 |