On 2013-12-06 17:35, De Santis Luca wrote:
Ciao Luca,
Vi ammorbo ancora con gli alberi. Devo fare una funzione per trovare
il path di una qualsiasi foglia di un albero.
Per fare ciò ho pensato di inserire nella classe che definisce
l’albero un campo nodoGenitore, così, facendo la ricerca di un nodo
per nome, quando trovo il nodo che mi interessa, vedo chi è il nodo
padre e vado a ritroso fino alla radice e trovo il path completo
della
foglia.
Questo di solito non è necessario negli algoritmi ricorsivi. Tra
l'altro in Python hai anche un problema: se hai due oggetti che si
riferiscono l'uno all'altro tipo (a.figli contiene b e b.genitore punta
ad a) hai un ciclo di riferimenti. Poiché Python distrugge gli oggetti
quando il refcount scende a zero questi due oggetti si tengono in vita
l'uno con l'altro e potresti avere un memory leak. Questo è molto
semplificato: il GC di Python è abbastanza intelligente di accorgersi di
molti casi in cui un ciclo di oggetti non ha riferimenti esterni e alla
fine riesce a reclamarlo, ma non sempre e così (quando non sia possibile
è un po' complesso, ma ben documentato). Per farla corta, meno cicli hai
nel codice, meglio è (e sempre a volerla dire tutta weakref è un modo
fatto apposta per avere cicli "rompibili", ma anche di questo non ne hai
bisogno per ora: la butto là in caso ti vada di approfondire).
Tornando a bomba: secondo me il puntatore del genitore non ti serve: il
tornare a ritroso te lo dà lo srotolamento dello stack quando la
soluzione viene trovata: io farei una funzione che interroga i figli e,
se uno di loro è positivo, aggiunge sé stesso al valore di ritorno (se
uno dei miei figli è la soluzione, anche io sono la soluzione!)
Quando un nodo è la soluzione? quando w == nomeNodo. Non ti serve
chiederlo ai figli, giusto? Penso ti sia infilato in un vicolo cieco
mentale facendo:
def _path(self,root,w):
for node in root.sottoNodi:
if(node.nomeNodo==w):
non serve chiederlo ai figli, e hai anche il problema che se root è la
soluzione, non la troverai, giusto?
Questa funzione deve restituire una lista di nodi: direi che se c'è una
soluzione sarebbe una lista che ha prima la radice, poi il suo figlio
che porta alla soluzione... fino alla soluzione. Essendo l'algoritmo
ricorsivo, puoi scriverlo in maniera che, gira gira, troverai un albero
la cui radice è la soluzione (che poi sia la radice complessiva o solo
un sotto-sotto-nodo non serve saperlo a lui: serve saperlo al
chiamante). Quindi qualcosa come:
def path(self, w):
# sono io la soluzione?
# sì: fico: restituisci una lista che contiene solo me stesso
# no? peccato, ma:
# per ognuno dei miei figli
# dammi il path per w
# è una lista? fico allora
# aggiungo me stesso all'inizio della lista
# e restituisco la lista a chi mi ha chiamato
questo l'ho scritto in pseudocodice, ma l'ho implementato anche in
python. Ti dò una possibilità di farlo da te se vuoi: letteralmente ogni
riga che ho scritto si trasforma in un'instruzione Python, ma così credo
sia ancora più chiaro l'algoritmo. Se vuoi la soluzione completa te la
passo (o te la passa qualcun altro).
Nota che se la parola non viene trovata in nessuno dei figli il flusso
di esecuzione esce alla fine della funzione senza incontrare un return.
Questo equivale a "return None", ed è il risultato alternativo di "è una
lista? fico". In pratica nodo.path(w) restituisce una lista se la
soluzione viene trovata, altrimenti None.
In bocca al lupo!
-- Daniele
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
