깊이 우선 검색으로 생성 된 노드의 총 수는 무엇입니까?

Question

가정 : 'd'는 트리의 유한 깊이입니다. 'b'는 분기 요인입니다. 'g'는 가장 얕은 목표 노드입니다.

내가 아는 바로는 최악의 경우는 목표 노드가 트리의 마지막 오른쪽 하단 노드에있는 경우입니다. 따라서 생성 된 총 노드 수는 O (bg)입니다. 맞습니까? 그러나 강사는 목표 노드를 루트로하는 하위 트리를 제외하고 모든 트리를 탐색 할 때 최악의 상황이 발생했기 때문에 잘못된 것이라고 말했습니다. 그는 O (bd) - O (b (g-d))에 대해 언급했습니다 .... 나는 완전히 확신하지 않습니다..

나는 그 사람이 의미하는 것을 정말로 얻지 못합니다. 그래서 어떤 사람이 어떤 대답이 옳은지 말해 줄 수 있습니까?

Answer 1

트리를 그려보고 탐색되는 노드를 표시하고 그 수를 계산하는 것이 좋습니다.

너비가 각 지점 (깊이가 O(b**g) 인 노드 수)에 도달했기 때문에 너비가 큰 첫 번째 검색을 사용하는 것이 맞습니다.

깊이 첫 번째 검색을 사용하는 경우 강사의 추론은 골이있는 부분 (O(b**d - b**(d-g)) 노드가 탐색 됨)을 제외한 모든 부분에 대해 깊이가 있기 때문에 정확합니다.

목표는 녹색 원이다.

파란색 노드가 탐색됩니다.

빨간색 노드는 탐색되지 않습니다.

탐구 한 수를 세기 위해 우리는 나무의 총계를 세고 빨간색 것들을 빼앗아갑니다. 깊이 I 트리 O(b**d)의 노드 수를 호출 한 = 1 = g

분기 계수 = B = 3

주에서

깊이 = 2 = D

하네요. 엄밀히 말하면 합계는 b**d + b**(d-1) + b**(d-2) + ... + 1이지만이 값은 O(b**d)입니다.