Ricerca soluzioni

La ricerca delle soluzioni consiste nel processo di selezione delle diverse possibilità di azione, a partire da uno stato iniziale, che permette l'individuazione di una sequenza di azioni in grado di risolvere un problema. Ogni sequenza possibile di azioni viene analizzata da parte dell'agente razionale o dell'algoritmo di selezione. Il processo di selezione è rappresentato graficamente tramite un albero di ricerca dove ogni nodo identifica uno stato dello spazio degli stati e ogni collegamento identifica una determinata azione all'interno di una sequenza di azioni. Nell'albero di ricerca ogni ramo è composto da più nodi e più collegamenti ed identifica una sequenza di azioni. Se la sequenza di azioni consente di giungere al risultato sperato, ossia alla soluzione del problema, la sequenza viene aggiunta alla lista delle soluzioni possibili. Il processo di ricerca delle soluzioni continua analizzando le altre sequenze di azioni possibili. Le modalità con cui si svolge il processo di ricerca soluzioni è detta strategia di ricerca.

  • Lista aperta. L'insieme di tutti i cammini ( sequenze di azioni ) ancora da analizzare è detto lista aperta. Nel momento in cui un cammino viene analizzato, questo viene rimosso dalla lista aperta. Il processo di ricerca soluzioni si conclude quando la lista aperta è un insieme vuoto.
  • Lista chiusa. L'insieme dei cammini ( sequenze di azioni ) già analizzati dal processo di ricerca soluzioni è detto lista chiusa. Quando un cammino viene analizzato dal processo di ricerca, questo viene aggiunto alla lista chiusa.

Il processo è detto ricerca soluzioni ottimale se analizzata tutte le sequenze di azioni della lista aperta. Un processo di ricerca soluzioni basato sull'utilizzo della lista aperta ( insieme da esplorare ) e della lista chiusa ( insieme esplorato ) consente di evitare di analizzare più volte gli stessi cammini e di evitare il problema dei cammini ridondanti, dei cammini ciclici e dei cicli infiniti ( loop ) dell'algoritmo di ricerca.

Ricerca soluzioni breve.La ricerca soluzioni può concludersi prima dell'esaurimento completo della lista aperta. Ciò può accadere, ad esempio, quando l'agente razionale deve individuare una soluzione accettabile in un lasso breve di tempo. Il processo si conclude con l'individuazione della prima sequenza di azioni ( cammino ) in grado di garantire una soluzione accettabile del problema che, pur non essendo necessariamente quella ottimale, garantisce sia un livello minimo di efficacia decisionale e sia un livello minimo di efficienza in termini di tempo e di risorse impiegate.

Memoria. L'utilizzo di algoritmi di ricerca basati sulla lista aperta e sulla lista chiusa necessitano di una quantità di memoria hardware per poter registrare i risultati parziali dell'elaborazione. In alcuni casi, la quantità di memoria necessaria potrebbe anche diventare eccessiva o comunque superiore alla quantità di memoria del sistema di elaborazione. È quindi opportuno analizzare la complessità dell'algoritmo di ricerca al fine di costruire preventivamente un'architettura hardware adeguata all'elaborazione.

https://www.okpedia.it/ricerca_soluzioni



note



25 / 05 / 2014


Ricerca soluzioni

Problemi