Fattore di ramificazione effettivo

Il fattore di ramificazione effettivo è un indicatore per misurare l'efficacia di una euristica in un algoritmo di ricerca informata. Data una ricerca informata si rileva il numero N dei nodi espansi dall'algoritmo prima di arrivare alla soluzione del problema e la profondità d. Il numero dei nodi N e la profondità d consentono di ricreare un albero di ricerca equivalente. Sapendo che:

N+1 = 1+b1+b2+b3+...+bd

è possibile determinare il fattore di ramificazione effettivo b nel seguente modo:

b = O(N1/(d+1))

Pur variando in ogni ricerca il fattore di ramificazione effettivo di una euristica tende a oscillare intorno a un valore costante. Quanto più il fattore di ramificazione tende a 1 tanto più l'euristica è efficiente nel costo di computazione. È così possibile comparare due o più euristiche individuando quella migliore (più efficiente) ossia quella con fattore di ramificazione più basso. Quando una euristica A è più efficiente di un'altra euristica B, si dice che l'euristica A domina sull'euristica B ( dominazione euristica ).

Ad esempio, in una ricerca informata viene rilevato un fattore di ramificazione effettivo pari a 1,6 con una euristica A e un fattore di ramificazione effettivo pari a 1,7 con una euristica B. L'euristica A domina sull'euristica B poiché consente un costo inferiore di computazione della ricerca.

https://www.okpedia.it/fattore_di_ramificazione_effettivo


Segnala un errore o invia un suggerimento per migliorare la pagina


Euristica

Informatica

Economia


FacebookTwitterLinkedinLinkedin