[AI] 트리 구조란

1. 트리 구조

트리 구조(Tree)는 그래프(Graph)의 일종이다.

 

트리 구조(Tree)

 

2. 노드(Node)

루트 노드(Root Node)는 부모(Parent)가 없는 노드를 의미한다.

리프 노드(Leaf Node)는 자식(Successor)이 없는 노드를 의미한다.

 

3. 깊이(Depth)

루트 노드의 깊이는 0이다. 하단으로 내려갈 수록 깊이가 증가한다.

 

깊이(Depth)

 

4. 탐색(Search)

루트 노드로부터 시작한다.

현재 노드(Current State)가 목표(Goal State)일 경우 종료(Finish), 목표가 아닐 경우 확장(Expand)한다. 목적지에 도달할 때 까지 반복한다.

어떠한 노드로 확장할 지에 대한 결정은 탐색 전략을 따른다.

 

Path, Length, Cost of Path

 

5. Path, Length, Cost of Path

출발지에서 목적지까지를 경로를 Path라 한다.

출발지에서 목적지까지의 거리를 Length라 한다.

Cost of Path는 arc를 모두 더할 경우 구할 수 있다.

6. Branching Factor

모든 노드의 자식이 같을 경우 이를 Branching Factor라 한다.

모든 노드가 2개의 자식을 가지고 있을 경우, Branching Factor는 2다.