PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A. La complessita' degli algoritmi di ricerca euristica. In: Atti del Congresso annuale A.I.C.A. (Genova, 326). Atti, pp. 323 - 326. 1975.
 
 
Abstract
(English)
No abstract available
Abstract
(Italiano)
Nel presente lavoro viene analizzata la complessità del algoritmi di ricerca euristica, cioè algoritmi che trovano il cammino di costo minimo in un grafo usando informazione euristica per guidare la ricerca. In particolare, si mostra che l'algoritmo A*, dovuto ad Hart, Nilsson e Raphael, può richiedere, nel caso peggiore, un numero di passi dell'ordine di 2N per cercare il cammino minimo in un grafo con N nodi. Inoltre viene presentato un nuovo algoritmo che, nel caso peggiore, esegue un numero di passi dell'ordine N2 e che, in nessun caso, esegue più passi dell'algoritmo A*. Il comportamento di questi algoritmi viene discusso usando com esempio il problema del commesso viaggiatore.
Subject


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional