아래 검색 트리에는 11 개의 노드가 있으며 그 중 5 개는 잎입니다. 10 개의 분기가 있습니다.
평균 분기 계수는 10/6 또는 10/11로 제공됩니까?
계산에 잎이 포함됩니까? 직관적으로 우리는 분기가있는 노드에 관심이 있기 때문에 그렇지 않다고 생각합니다. 하지만 교수님이 제게 부여한 정의는 “나무에있는 모든 노드의 평균 가지 수”로 잎이 포함되어 있음을 의미합니다.
댓글
- 좋은 질문입니다. ' " ai-basics " 태그를 자유롭게 추가했습니다. Stack : AI에 오신 것을 환영합니다!
Answer
나는 잎이 그 자체로 도 계산되지만 “체크 메이트 위치와 같이 실제 나뭇잎 인 경우에만 해당됩니다.
이러한 노드에는 실제로 자식이 없으며 추가 계산이 필요하지 않습니다. 아직 확장되지 않은 노드와는 다릅니다.
항상 잎을 확실하게 세면 (n-1)/n 모든 n -node thee!
답변
위키 백과에서 :
컴퓨팅, 트리 데이터 구조 및 게임 이론에서 분기 요소는 각 노드의 자식 수입니다. , outdegree .이 값이 균일하지 않으면 평균 분기 계수를 계산할 수 있습니다.
Outdegree 의미-유 방향 그래프의 경우 들어가는 간선 수 노드는 해당 노드의 in-degree라고하며 노드에서 나오는 에지의 수는 해당 노드의 out-degree라고합니다.
outdegree 부분. AI에서는 일반적으로 한 상태에서 다른 상태로 방향성 그래프를 그리고 outdegree 는 특정 노드를 떠나는 경로의 수입니다. 그래프 방향은 제공되지 않습니다. 또한 그래프는 대칭이 아니지만 여기 에서 주어진 비대칭 방향성 그래프의 분기 요소 (약간 어려움)를 찾을 수 있습니다. 따라서 기술적으로 리프 노드가 계산되지 않는 것에 대한 결론은 정확합니다 (다른 상태에 도달 할 수없는 마지막 상태 인 데드 엔드라고 가정). 도움이 되었기를 바랍니다.