I søgetræet nedenfor er der 11 noder, hvoraf 5 er blade. Der er 10 grene.
Gives den gennemsnitlige forgreningsfaktor ved 10/6 eller 10/11?
Er blade inkluderet i beregningen? Intuitivt tror jeg ikke, da vi er interesserede i noder med grene. En definition, der blev givet af min professor, var “Det gennemsnitlige antal grene af alle noder i træet”, hvilket ville antyde, at blade er inkluderet.
Kommentarer
- Fantastisk spørgsmål. Jeg ' har taget friheden til at tilføje " ai-basics " tag. Velkommen til Stack: AI!
Svar
Jeg siger, at bladene per se tæller også, men kun hvis de er rigtige blade, som f.eks. skakmatpositioner i skak.
En sådan node har virkelig ingen børn, og der er ikke behov for yderligere beregning. I modsætning til noder, der endnu ikke var udvidet.
Bemærk at altid at tælle bladene beviseligt fører til (n-1)/n for hver n -node dig!
Svar
Fra Wikipedia:
I computing, trædatastrukturer og spilteori er forgreningsfaktoren antallet af børn ved hver node , outdegree . Hvis denne værdi ikke er ensartet, kan en gennemsnitlig forgreningsfaktor beregnes.
Udgående betyder – I tilfælde af rettet graf, antal kanter, der går ind en node er kendt som en grad af den tilsvarende node, og antallet af kanter, der kommer ud af en node, er kendt som en udgang af den tilsvarende node.
Du har glemt outdegree del. I AI vi tegner eneralt rettet grafer fra en tilstand til en anden, og outdegree er antallet af stier, der forlader en bestemt node. Retning er ikke angivet i din graf. Også din graf er ikke symmetrisk, men du kan stadig finde ud af forgreningsfaktoren (med lidt besvær) for ikke-symmetrisk rettet graf som angivet her . Så teknisk set er din konklusion korrekt, om bladnoder ikke tælles (forudsat at de er den sidste tilstand, hvorfra ingen anden tilstand kan nås – blindgyde). Håber dette hjælper!