Ingår lövnoder i beräkningen av den genomsnittliga förgreningsfaktorn för sökträd?

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.

Sökträd

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!

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *