브랜치와 바운드에서 너비 우선 검색의 메모리 문제를 이해하는 방법

Question

최근 브랜치와 바운드 방식에 혼란 스러웠습니다. 브랜치 앤드 바운드 방식에는 깊이 우선 검색, 폭 우선 검색 및 최상 우선 검색이라는 세 가지 검색 전략이 있습니다. 모든 책과 문헌에 따르면 폭과 우선은 컴퓨터가 사용하는 메모리를 더 많이 차지합니다. 이것을 이해하는 방법? 예를 들어, 라이브 노드 목록에서 노드 (아버지 노드)를 처리 할 때 2 개의 하위 노드 (또는 아들 노드)가 생성되어 활성 노드 목록에 삽입되지만이 노드는 삭제되어야합니다 따라서 하나의 노드에서 메모리가 증가합니다. 이러한 관점에서 볼 때 세 가지 검색 전략 모두 컴퓨터의 동일한 기억을 취합니다. 맞습니까? 오랫동안 혼란 스러웠습니다. 아무도 내게 약간의 조언을 줄 수 있습니까? 당신은 데이터 구조에 대해 생각할 수있는

Answer 1

음 :

폭 우선 검색 : 오기 '큐로 구현. 노드 (아버지 노드)를 확장하면 아들 노드가 대기열에 포함됩니다. 아버지 노드가 삭제됩니다. 그래서 45를 우리는 큐 20과 70을 포함 삭제 :

1. 이 45를 확장 Let's는 예를하게

   20 | 70

2. 20를 확장 : 우리는 큐에서 첫 번째 노드를 확장하고 그의 아들을 포함한다 :

   70 | 10 | 28

3. 70를 확장 : 우리는 큐에서 첫 번째 노드를 확장하고 그의 아들을 포함한다 :

   10 | 28 | 60 | 85

   기타 등등 ...만약 공간 복잡성시피

는 지수이다 O () (B = 인자 분파; D = 깊이 초기 0)

Deepth 우선 검색 : 그것을

,536,913,632 : 스택으로 구현 것 우리는 스택 (20) 및 (70)을 포함하고 있으므로 45 삭제 : 10

1. 45를 확장

   20 | 70

2. 20를 확장 : 우리는 스택의 상단에서 첫 번째 노드를 확장하고 그의 아들을 포함한다 :

   10 | 28 | 우리는 스택의 상단에서 첫 번째 노드를 확장하여 그의 아들과 같습니다 : 70

3. 10를 확장

   1 | 18 | O (d) : | 28

70

등등 ... 편지 공간 복잡도 선형이다. 시간 복잡도는 두 알고리즘에서 O ()입니다.

최고 우선 검색 : 정렬 (N) 휴리스틱 평가 함수 F에 따르면 큐 최고의 F (N)과 succesor 확장. 공간 복잡성은 선형입니다 : O (d).

희망이 도움이됩니다.