Alla olevassa hakupuussa on 11 solmua, joista 5 on lehtiä. Haaroja on 10.
Onko keskimääräinen haarautumiskerroin annettu 10/6 vai 10/11?
Sisällytetäänkö lehdet laskelmaan? En uskoisi intuitiivisesti, ettei, koska olemme kiinnostuneita oksilla olevista solmuista. Professorini minulle antama määritelmä oli kuitenkin ”Puun kaikkien solmujen keskimääräinen haaramäärä”, mikä merkitsisi, että lehdet ovat mukana.
Kommentit
- Hyvä kysymys. Olen ' ottanut itselleni vapauden lisätä " ai-perusasiat " -tunniste. Tervetuloa Stackiin: AI!
Vastaa
sanoisin, että lehdet sinänsä lasketaan myös, mutta vain, jos he ovat todellisia lehtiä, kuten esimerkiksi shakkimatkojen sijainnit.
Tällaisella solmulla ei todellakaan ole lapsia, eikä lisälaskelmia tarvita. Toisin kuin solmuissa, jotka eivät ole vielä laajentuneet.
Huomaa, että aina lehtien laskeminen todistettavasti johtaa (n-1)/n jokaiselle n -solmulle!
Vastaa
Wikipediasta:
Laskennassa, puun tietorakenteissa ja peliteoriassa haarautumistekijä on kunkin solmun lasten määrä , outdegree . Jos tämä arvo ei ole yhtenäinen, voidaan laskea keskimääräinen haarautumiskerroin.
Outdegree merkitys – Suunnattujen kuvaajien ollessa kyseessä reunojen lukumäärä solmu tunnetaan vastaavan solmun asteina ja solmusta ulos tulevien reunojen lukumäärä tunnetaan vastaavan solmun ulommana asteena.
Unohdit outdegree osa. AI: ssä g piirtää suunnattuja kuvaajia yhdestä tilasta toiseen, ja outdegree on tietystä solmusta lähtevien polkujen määrä. Kaaviosi suunta ei ole annettu. Kuvaajasi ei myöskään ole symmetrinen, mutta voit silti selvittää epäsymmetristen suunnattujen kuvaajien haarautumistekijän (pienillä vaikeuksilla) täältä . Joten teknisesti johtopäätöksesi on oikea siitä, että lehtisolmuja ei lasketa (olettaen, että ne ovat viimeinen tila, josta ei voida saavuttaa muuta tilaa – umpikuja). Toivottavasti tämä auttaa!