반복 트리

Question

내가 재귀 트리 탐색을 할 수 방법 (TM)하지 않을 수 있다는 제안에 의해 최근 데이터 구조와 알고리즘 대학했다, 그래서 나는 놀랐다 이후가 꽤있었습니다. 어떤 이유로 반복적 인 큐 기반 트래버스는 내가 지금까지 사용해 본 기술이 아닙니다.

반복적 반복 탐색의 장점은 무엇입니까? 어떤 상황에서 다른 상황보다 하나를 사용할 수 있습니까?

Answer 1

광범위한 검색을 수행하는 경우 자연스러운 구현은 반복을 사용하지 않고 노드를 대기열에 밀어 넣는 것입니다.

심도있는 첫 번째 검색을 수행하는 경우 재귀가 통과를 코딩하는 가장 자연스러운 방법입니다. 그러나 컴파일러가 반복에 꼬리 재귀를 최적화하지 않으면 재귀 구현이 반복 알고리즘보다 느려지고 트리가 충분히 깊은 곳에서 스택 오버플로가 발생하여 죽을 것입니다.

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)))), (3, (5, (8)))) 
def bfs(t): 
    to_visit = [t] 
    while len(to_visit) > 0: 
     c = to_visit[0] 
     if type(c) is int: 
      print c 
     else: 
      print c[0] 
      to_visit.append(c[1]) 
      if len(c) > 2: to_visit.append(c[2]) 
     to_visit = to_visit[1:] 

def dfs(t): 
    if type(t) is int: 
     print t 
     return 
    print t[0] 
    dfs(t[1]) 
    if len(t) > 2: dfs(t[2]) 

bfs(t) 
dfs(t) 

Answer 2

그것은 당신이 깊이 우선 또는 너비 우선 탐색을 수행 할 것인지 여부에 따라 달라집니다

빠른 파이썬

그 차이를 설명하기 위해. Depth-first는 재귀를 통해 구현하는 것이 가장 쉽습니다. 폭 넓은 우선 순위를 사용하면 앞으로 확장 될 노드 대기열을 유지해야합니다.

Answer 3

스택 전용 고정량의 메모리가있는 경우 자주 발생하며 (특히 많은 Java JVM 구성에서이 문제가 특히 많이 발생 함) 깊은 트리가있는 경우 재귀가 제대로 작동하지 않을 수 있습니다 (재귀 깊이 다른 시나리오에서는 높음). 스택 오버플로가 발생합니다. 반복적 접근법, 노드를 큐 (BFS와 같은 트래버스 용) 또는 스택 (DFS와 같은 트래버스 용)으로 방문하게하는 방법은 여러 가지면에서 더 나은 메모리 특성을 가지므로이 문제가 반복되는 접근법을 사용하십시오.

재귀의 장점은 표현/표현의 단순성이며 성능이 아닙니다. 이를 기억하는 것은 주어진 알고리즘, 문제 크기 및 기계 아키텍처에 대한 적절한 접근법을 선택하는 열쇠입니다.

Answer 4

실제로는 너비가 큰 첫 번째 검색에 큐를 사용하고 깊이 우선 검색을 위해 스택 을 사용하고 while 루프에서 알고리즘을 실행해야합니다. 탐색 중에 함수를 호출하면 간단히 작업을 수행하면 스택을 오버플로 할 수 있으므로 프로그램을 크게 드래그 할 수 있지만 최근에는 을 열심히 시도해야합니다.

나무가 아니라 잘 연결된 그래프 인 경우 이미 방문한 노드를 추적하기 위해 측면에 해시가 있습니다.

Answer 5

실제로 스택 오버플로 오류가 발생할 수 있기 때문에 재귀 적으로 이동해야하며, 결국 stackoverflow.com입니다.