W drzewie wyszukiwania poniżej znajduje się 11 węzłów, z których 5 to liście. Jest 10 gałęzi.
Czy średni współczynnik rozgałęzień jest podany przez 10/6 lub 10/11?
Czy w obliczeniach uwzględniono liście? Intuicyjnie nie sądzę, ponieważ interesują nas węzły z rozgałęzieniami. Jednak definicja podana mi przez mojego profesora brzmiała „Średnia liczba gałęzi wszystkich węzłów w drzewie”, co sugerowałoby, że uwzględniono liście.
Komentarze
- Świetne pytanie. ' pozwoliłem sobie na dodanie tagu " ai-basics ". Witamy w Stack: AI!
Odpowiedź
Powiedziałbym, że liście per se też liczą, ale tylko wtedy, gdy są prawdziwymi liśćmi, jak np. pozycje mata w szachach.
Taki węzeł naprawdę nie ma dzieci i nie są potrzebne żadne dalsze obliczenia. W przeciwieństwie do węzłów, które nie zostały jeszcze rozwinięte.
Zauważ, że zawsze liczenie liści w sposób możliwy do ustalenia prowadzi do (n-1)/n za każde n -węzeł ciebie!
Odpowiedź
Z Wikipedii:
W obliczeniach, drzewiastych strukturach danych i teorii gier czynnikiem rozgałęzienia jest liczba dzieci w każdym węźle , outsideegree . Jeśli ta wartość nie jest jednolita, można obliczyć średni współczynnik rozgałęzienia.
Outdegree znaczenie – w przypadku wykresów skierowanych liczba krawędzi wchodzących w węzeł jest znany jako stopień w odpowiednim węźle, a liczba krawędzi wychodzących z węzła jest określana jako stopień poza odpowiednim węzłem.
Zapomniałeś o Outdegree część. W sztucznej inteligencji g generalnie rysuj skierowane wykresy z jednego stanu do drugiego, a outsideegree to liczba ścieżek opuszczających określony węzeł. Na twoim wykresie kierunek nie jest podany. Również twój wykres nie jest symetryczny, ale nadal możesz znaleźć współczynnik rozgałęzienia (z niewielką trudnością) niesymetrycznych skierowanych wykresów, jak podano tutaj . Więc technicznie twój wniosek jest poprawny, że węzły liści nie są liczone (zakładając, że są to ostatni stan, z którego nie można osiągnąć żadnego innego stanu – ślepy zaułek). Mam nadzieję, że to pomoże!