는 깊이 우선 검색에 대해

Question

위키 백과를 역 추적의 관점에서 BFS와 DFS 설명 :

깊이 우선 검색 (DFS)이 통과 또는 트리, 트리 구조, 또는 그래프를 검색하는 알고리즘이다. 하나의 은 루트에서 시작하여 ( 노드를 그래프의 경우 루트로 선택) 및 가능한 한 멀리 각 분기 전에 을 탐색합니다.

그렇다면 Breadth First Search 란 무엇입니까?

"시작 노드를 선택하는 알고리즘은 모든 노드에게이 는 최단 경로를 선택 역 추적을 확인하여 선택 이웃이 는 최단 경로를 선택 역 추적 노드, 마지막으로 는 최적의 경로 때문에 발견 으로 인해 연속 되돌아 각 경로를 탐색.

정규식 find 님의 가지 치기 - 역 추적?

역 추적이라는 용어는 다양한 용도로 인해 혼란 스럽습니다. UNIX의 find SO 사용자를 프 루닝하는 것은 역 추적으로 설명됩니다. Regex의 범위를 제한하지 않으면 Regex Buddy는 "catastrophic backtracking"이라는 용어를 사용합니다. 너무 광범위하게 사용되는 우산 용어 인 것 같습니다. 따라서 :

1. 그래프 이론을 위해 특별히 "백 트랙킹"을 어떻게 정의합니까?
2. 넓은 검색 우선 순위 및 심도 우선 검색에서 "역 추적"이란 무엇입니까?

[추가]

좋은 역 추적에 대한 정의와 예

1. The Brute-force method

2. 스톨만의 (?) 발명 용어 "dependency-directed backtracking"
3. 역행하고 regex 예를
4. Depth First Search definition.

Answer 1

되돌아가 검색 중에 일어나는 일이지만, 그것은 또한 되돌아 많이 수행되는 특정 문제 해결 기법을 의미하기 때문에 혼란이 온다. 이러한 프로그램을 백 트래커라고합니다.

이웃으로 운전하는 사진. 막 다른 골목에 도달 할 때까지 항상 첫 번째 회전을 봅니다. 그 시점에서 다음 방문하지 않은 거리의 교차로로 돌아옵니다. 이것은 "처음"되돌아 오는 종류이며, 단어의 구어체 사용과 대략 동일합니다.

더 구체적인 사용법은 깊이 우선 검색과 비슷하지만 일부 하위 트리를 계속할 가치가 없다는 것을 알았을 때 다시 추적하는 문제 해결 전략을 의미합니다.

다시 말해서 순진한 DFS는 맹목적으로 목표에 도달 할 때까지 각 노드를 방문합니다. 예, 리프 노드에서 "역 추적"됩니다. 그러나 backtracker도 쓸모없는 지점으로 되돌아갑니다. 한 가지 예는 Boggle 보드에서 단어를 검색하는 것입니다. 각 타일은 8 개의 다른 타일로 둘러싸여있어 나무가 큽니다. 순진한 DFS는 너무 오래 걸릴 수 있습니다. 그러나 "ZZQ"와 같은 조합을 볼 때 더 많은 글자를 추가해도 단어가 나오지 않으므로이 시점부터 검색을 중단 할 수 있습니다.

나는 Julie Zelenski 교수의 강의를 매우 좋아합니다. 그녀는 8 퀸, 스도쿠 퍼즐, 백 트랙킹을 이용한 숫자 대체 퍼즐을 해결하고 모든 것이 멋지게 움직입니다. Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

나무는 임의의 두 정점은 그들 사이에 하나 개의 경로가 그래프이다. 이것은 사이클의 가능성을 제거합니다. 그래프를 검색 할 때 대개 어쨌든 사이클을 제거하는 논리가 있으므로 행동은 동일합니다. 또한 유향 그래프에서는 "잘못된"방향으로 가장자리를 따라갈 수 없습니다.

Stallman 논문에서 그들은 쿼리에서 "예"또는 "아니오"라고 말하는 것이 아니라 실제로 가장 적은 수의 변경으로 잘못된 쿼리에 대한 수정을 제안하는 논리 시스템을 개발했습니다. 역 추적의 첫 번째 정의가 어디에서 작용할지 알 수 있습니다.