제한된 메모리를 사용하는 반복적 인 심화 깊이 검색

Question

이것은 Find first null in binary tree with limited memory의 후속 조치입니다.

위키피디아에서는 반복 깊이가 심화되는 첫 번째 검색이 최단 경로를 찾을 것이라고 말합니다. 나는 k 노드에 메모리가 제한되어 있으며 가장 적은 횟수의 트리에 액세스하는 구현을 원한다.

예를 들어, 내 이진 트리 인 경우 :

  0 
    1    2 
3 4  5  6 
7 8 9 10 11 12 13 14 

그리고 내 검색 순서와 메모리의 5 개 노드로 제한 해요 것은 :

이

mem[0] = read node 0 
mem[1] = read node 1 
mem[2] = read node 2 
mem[3] = read node 3 
mem[4] = read node 4 //Now my memory is full. I continue... 
mem[3] = read node 5 //overwrite where I stored node 3 
mem[4] = read node 6 //overwrite where I stored node 4 

지금 내 옆에 읽기가있는 경우 7, 나는 3을 다시 읽어야한다. 그러나 만약 내가 다음에 14를 읽게한다면, 나는 아직 3을 다시 읽을 필요가 없다. 솔루션이 14 일 경우 알고리즘이 조금 빨라집니다!

일반적인 해결책을 찾고 있습니다. 어떤 크기의 메모리와 노드 당 브랜치의 수를 위해 작동 할 것입니다.

Answer 1

노드가 부모와 연결되어 있고 노드의 자식이 항상 같은 순서로 열거되는 경우 저장하지 않고도 단계를 추적 할 수 있습니다.