I søketreet nedenfor er det 11 noder, hvorav 5 er blader. Det er 10 grener.
Er den gjennomsnittlige forgreningsfaktoren gitt av 10/6, eller 10/11?
Er blader inkludert i beregningen? Intuitivt vil jeg ikke tro det, siden vi er interessert i noder med grener. En definisjon gitt av professoren min var imidlertid «Gjennomsnittlig antall grener av alle noder i treet», noe som ville antyde at blader er inkludert.
Kommentarer
- Flott spørsmål. Jeg ' har tatt meg friheten til å legge til " ai-basics " -koden. Velkommen til Stack: AI!
Svar
Jeg vil si at bladene per se teller også, men bare hvis de er reelle blader, som f.eks. sjakkmatposisjoner i sjakk.
En slik node har egentlig ingen barn, og det er ikke behov for ytterligere beregning. I motsetning til noder som ikke var utvidet ennå.
Merk at å alltid telle bladene beviselig fører til (n-1)/n for hver n -node deg!
Svar
Fra Wikipedia:
I databehandling, tredatastrukturer og spillteori er forgreningsfaktoren antall barn ved hver node , utegrad . Hvis denne verdien ikke er ensartet, kan en gjennomsnittlig forgreningsfaktor beregnes.
Outdegree betydning – I tilfelle av rettet graf, antall kanter som går inn i en node er kjent som in-grad av den tilsvarende noden, og antall kanter som kommer ut av en node er kjent som ut-grad av den tilsvarende noden.
Du har glemt outdegree del. I AI vi tegne eneralt rettet grafer fra en tilstand til en annen, og outdegree er antall baner som forlater en bestemt node. I grafen din er retning ikke gitt. Grafen din er heller ikke symmetrisk, men du kan fremdeles finne ut forgreningsfaktoren (med litt vanskeligheter) for ikke-symmetrisk rettet graf som gitt her . Så teknisk sett er konklusjonen din riktig om at bladnoder ikke telles (forutsatt at de er den siste tilstanden som ingen annen tilstand kan nås fra – blindvei). Håper dette hjelper!