I sökträdet nedan finns 11 noder, varav 5 är löv. Det finns tio grenar.
Är den genomsnittliga förgreningsfaktorn angiven av 10/6 eller 10/11?
Ingår löven i beräkningen? Intuitivt skulle jag inte tro det, eftersom vi är intresserade av noder med grenar. En definition som jag fick av min professor var dock ”Det genomsnittliga antalet grenar av alla noder i trädet”, vilket skulle innebära att blad ingår.
Kommentarer
- Stor fråga. Jag ' har tagit mig friheten att lägga till " ai-basics " -taggen. Välkommen till Stack: AI!
Svar
Jag skulle säga att bladen per se räknar också, men bara om de är riktiga löv, som t.ex. schackmattpositioner i schack.
En sådan nod har egentligen inga barn och ingen ytterligare beräkning behövs. Till skillnad från noder som inte har expanderats ännu.
Observera att alltid räknar löven bevisligen leder till (n-1)/n
för varje n
-nod dig!
Svar
Från Wikipedia:
I databehandling, träddatastrukturer och spelteori är förgreningsfaktorn antalet barn i varje nod , utgraderar . Om detta värde inte är enhetligt kan en genomsnittlig förgreningsfaktor beräknas.
Outgradering betyder – Vid riktade grafer, antal kanter som går in i en nod kallas ingrad för motsvarande nod och antalet kanter som kommer ut från en nod kallas utgrad för motsvarande nod.
Du glömde outdegree del. I AI vi g ritar eneralt riktade grafer från ett tillstånd till ett annat, och utgraderad är antalet vägar som lämnar en viss nod. I din graf anges inte riktning. Även din graf är inte symmetrisk, men du kan fortfarande ta reda på förgreningsfaktorn (med lite svårighet) för icke-symmetriskt riktade grafer enligt här . Så tekniskt sett är din slutsats korrekt om bladnoder inte räknas (förutsatt att de är det sista tillståndet från vilket inget annat tillstånd kan nås – återvändsgränd). Hoppas det hjälper!