Ricerca a costo uniforme
La ricerca a costo uniforme è una strategia di ricerca non informata in cui l'algoritmo espande il nodo sulla frontiera con il costo di cammino più basso dal nodo iniziale ( nodo radice ). Questa tipologia di ricerca, a differenza della ricerca in ampiezza, si presta ad essere utilizzata in caso di costi di passo non uguali nell'albero di ricerca, purché questi siano sempre non negativi. La condizione di "non negatività" dei costi di passi equivale a dire che in un medesimo cammino il costo di cammino è sempre non decrescente. La ricerca a costo uniforme permette di trovare la soluzione più economica tra le diverse sequenze di scelte possibili, senza necessariamente dover analizzare l'intero albero di ricerca. Facciamo un semplice esempio per comprendere la logica di funzionamento di un algoritmo di ricerca a costo uniforme.
Nell'esempio precedente l'agente razionale deve trovare il percorso più economico per arrivare al nodo di destinazione D a partire dal nodo di partenza A. I numeri sugli archi rappresentano il singolo costo di passo da un nodo all'altro. Inizialmente, nella fase 1, l'algoritmo espande i nodi successori B e C, calcola i rispettivi costi di cammino da A e sceglie il nodo successore con costo di cammino inferiore, ossia il nodo B (AB=2). Nella fase 2 espande dal nodo B il nodo successore D, ottenendo il costo di cammino ABD pari a 2+4=6. Come si può notare, l'algoritmo ha raggiunto l'obiettivo (D), tuttavia il costo del cammino ABD (6) risulta essere maggiore del costo del cammino AC (3). Pertanto, l'algoritmo non interrompe la ricerca. Nella fase 3 torna al nodo C e da qui espande il nodo D, calcolando il costo di cammino ACD (3+1=4). L'algoritmo di ricerca raggiunge nuovamente il nodo obiettivo (D) passando per il cammino ACD. Essendo il costo del cammino ACD (4) inferiore al costo del cammino ABD (6) e non essendoci altri archi a costo di cammino inferiore ancora da analizzare, la ricerca a costo uniforme si interrompe e restituisce il risultato finale.
