I nodi foglia sono inclusi nel calcolo del fattore di ramificazione medio per gli alberi di ricerca?

Nellalbero di ricerca sottostante, ci sono 11 nodi, 5 dei quali sono foglie. Ci sono 10 rami.

Il fattore di ramificazione medio è dato da 10/6 o 10/11?

Le foglie sono incluse nel calcolo? Intuitivamente, penserei di no, dal momento che siamo interessati ai nodi con rami. Tuttavia, una definizione data dal mio professore era “Il numero medio di rami di tutti i nodi dellalbero”, il che implica che le foglie siano incluse.

Cerca nella struttura

Commenti

  • Ottima domanda. Mi ' mi sono preso la libertà di aggiungere il tag " ai-basics ". Benvenuto in Stack: AI!

Risposta

Direi che le foglie di per sé conta, ma solo se sono vere foglie, come ad esempio posizioni di scacco matto negli scacchi.

Un nodo del genere non ha figli e non sono necessari ulteriori calcoli. A differenza dei nodi che non sono stati ancora espansi.

Nota che il conteggio sempre delle foglie provabilmente porta a (n-1)/n per ogni n -node te!

Risposta

Da Wikipedia:

In informatica, strutture di dati ad albero e teoria dei giochi, il fattore di ramificazione è il numero di figli in ogni nodo , outdegree . Se questo valore non è uniforme, è possibile calcolare un fattore di ramificazione medio.

Outdegree significato – In caso di grafici diretti, numero di bordi che entrano un nodo è noto come in grado del nodo corrispondente e il numero di bordi che escono da un nodo è noto come fuori grado del nodo corrispondente.

Hai dimenticato il outdegree part. In AI we g disegnare eneralmente grafici diretti da uno stato allaltro, e outdegree è il numero di percorsi che lasciano un particolare nodo. Nel tuo grafico la direzione non è data. Inoltre il tuo grafico non è simmetrico, ma puoi ancora scoprire il fattore di ramificazione (con un po di difficoltà) di grafici diretti non simmetrici come indicato qui . Quindi tecnicamente la tua conclusione è corretta sul fatto che i nodi foglia non vengono contati (supponendo che siano lultimo stato da cui non è possibile raggiungere nessun altro stato – vicolo cieco). Spero che questo aiuti!

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *