Cammino ciclico

Un cammino ciclico è un tipo di cammino ridondante che si verifica in alcuni algoritmi di ricerca quando il ciclo di ricerca diventa infinito. Ciò può accadere per diverse ragioni. Generalmente un cammino diventa ciclico quando si verifica uno stato ripetuto all'interno di una medesima sequenza di azioni. Facciamo un esempio pratico, ipotizziamo che l'algoritmo cerchi una strada per andare da A a D. Come si può osservare nel grafico sottostante l'algoritmo può diventare ciclico nel nodo C poiché l'algoritmo potrebbe tornare al nodo A ( stato ripetuto ) invece di dirigersi verso il nodo D.

L'esempio è volutamente molto semplice. I cammini ciclici possono aumentare notevolmente l'impiego delle risorse macchine e il tempo di esecuzione dell'algoritmo In alcuni casi il ciclo può diventare anche infinito ( loop ). In genere i cammini ciclici si presentano a causa di condizioni dell'algoritmo non previste in fase di progettazione. Essendo difficile ex-ante prevedere ogni possibile situazione, si ricorre ad apposite tecniche per evitare il cammino ciclico. Alcune possibili soluzioni al problema dei cammini ciclici sono le seguenti:

• Evitare stati ripetuti. Inserire una condizione per evitare di far ripercorrere un medesimo nodo ( stato ) in una stessa sequenza di azioni. Se lo scopo dell'algoritmo è di giungere da A a D, è inutile tornare al nodo A una volta giunti al nodo C. Questa tecnica è efficace soltanto se l'algoritmo non prevede la possibilità dell'agente razionale di tornare indietro da una scelta ( reversibilità delle decisioni ).
• Limite massimo del costo del cammino. Calcolare il costo del cammino e interrompere la ricerca non appena il costo è superiore al minore costo trovato fino a quel momento dall'algoritmo La tecnica è efficace soltanto se i costi del cammino sono non negativi.
• Lista aperta e chiusa. Rimuovere le sequenze già analizzate dall'insieme dell'universo da esplorare ( lista aperta ) e trasferirle nell'insieme dell'universo già esplorato ( lista chiusa ). Ciò implica, tuttavia, un maggiore consumo in termini di risorsa memoria poiché l'algoritmo dovrà registrare in memoria tutte le sequenze di azioni già analizzate.
• Riformulazione del problema. Riformulare il problema da risolvere in modo diverso al fine di evitare il problema del cammino ciclico. Talvolta il problema del cammino ciclico può essere evitato formulando diversamente il problema.
• Uscita forzata dal loop. È una condizione di sicurezza che, pur non eliminando il rischio dei cammini ciclici, riduce le conseguenze dei loop. Ad esempio, se un medesimo stato viene ripercorso più di N volte in una medesima sequenza, l'algoritmo si interrompe automaticamente o si limita ad interrompere la ricerca su quel ramo dell'albero di ricerca per iniziarne l'analisi del ramo successivo.