ciao a tutti,
avevo implementato una funziona ricorsiva il cui scopo è quello di individuare tutti i percorsi su un grafo.
Per sommi capi il codice richiama una funziona calcolaCammini(Percorso Soluzione, int posizione).
Soluzione è un oggetto che al suo interno istanzia un ArrayList dei nodi del grafo. Posizione invece indica la i-esima posizione nel cammino per la quale si sta scegliendo il nodo.
codice:
private void calcolaCammini(Percorso soluzione, int posizione) {
if(in soluzione(posizione) c'è l'ultimo nodo del grafo)
{
cammini.add((Percorso)soluzione.clone());
}
else {
posizione+=1;
nodiCandidati= insieme dei possibili nodi da inserire in soluzione(posizione);
Iterator it = nodiCandidati.iterator();
while (it.hasNext()) {
Vertice elemento = (Vertice)it.next();
Percorso copiaPercorso=(Percorso)soluzione.clone();
(copiaPercorso).aggiornaPath(elemento);
calcolaCammini(copiaPercorso,posizione);
}
}
}
Ho utilizzato il metodo clone per effettuare una copia di "soluzione" che passo alla funzione ricorsiva altrimeti anche se l'avessi aggiunta a cammini me la cambiava quando iniziava a risalire lungo la funzione ricorsiva. Vi faccio un esempio per farvi capire cosa succedeva non usando un clone.
mettiamo che io aggiunga a cammini la stringa "ciao" (dove 'c' è un nodo, 'i' è il successivo e cosi via).
Ora la funzione ricorsiva inizia a risalire.. e trova una nuova soluzione "ciaa" e l'aggiunge in cammini. In cammini avrò ora "ciaa" e "ciaa".
Il problema è che visto che alcune volte il grafo è enorme.. supero la dimensione dell'heap.
Volevo sapere.. c'è un modo per evitare questi clone?