În arborele de căutare de mai jos, există 11 noduri, dintre care 5 sunt frunze. Există 10 ramuri.
Este factorul mediu de ramificare dat de 10/6 sau 10/11?
Frunzele sunt incluse în calcul? Intuitiv, aș crede că nu, deoarece ne interesează nodurile cu ramuri. Cu toate acestea, o definiție pe care mi-a dat-o profesorul meu a fost „Numărul mediu de ramuri ale tuturor nodurilor din arbore”, care ar implica frunze sunt incluse.
Comentarii
- Întrebare excelentă. Am ' am luat libertatea de a adăuga eticheta " ai-basics ". Bine ați venit la Stack: AI!
Răspuns
Aș spune că frunzele în sine contează, de asemenea, dar numai dacă sunt frunze reale, cum ar fi, de exemplu, pozițiile de șah mat în șah.
Un astfel de nod nu are cu adevărat copii și nu este nevoie de alte calcule. Spre deosebire de nodurile care încă nu au fost extinse.
Rețineți că numărarea întotdeauna a frunzelor probabil duce la (n-1)/n pentru fiecare n -node tine!
Răspuns
Din Wikipedia:
În calcul, structuri de date în arbori și teoria jocurilor, factorul de ramificare este numărul de copii la fiecare nod , outdegree . Dacă această valoare nu este uniformă, se poate calcula un factor mediu de ramificare.
Outdegree sens – În cazul graficelor direcționate, numărul de muchii care intră în un nod este cunoscut sub numele de gradul corespunzător al nodului și numărul de muchii care ies dintr-un nod este cunoscut sub numele de gradul exterior al nodului corespunzător.
Ați uitat outdegree parte. În AI vom g desenează în mod general grafice direcționate de la o stare la alta și outdegree este numărul de căi care părăsesc un anumit nod. În grafic, direcția nu este dată. De asemenea, graficul dvs. nu este simetric, dar puteți afla totuși factorul de ramificare (cu puțină dificultate) a graficelor direcționate nesimetric, așa cum este dat aici . Deci, din punct de vedere tehnic, concluzia dvs. este corectă cu privire la faptul că nodurile frunzelor nu sunt numărate (presupunând că acestea sunt ultima stare din care nu se poate ajunge la nicio altă stare – impasul). Sper că acest lucru vă va ajuta!