Newsgroup: it.scienza.informatica
Titolo: Algoritmo ricerca sottoalberi

Ho realizzato un alogoritmo in java che preso in input un albero e un 
tipo di nodo di partenza A e uno di arrivo B trova tutti i cammini del 
tipo A--->B
Utilizzo una visita anticipata per visitare l'albero (complessità n) 
tramite una procedura ricorsiva
Utilizzo una struttura di supporto che contiene tutti i cammini 
iniziati: una insieme di liste che rappresentano i cammini iniziati fino 
  a quel punto
Uso un contenitore per memorizare i cammini completati
Ad ogni nodo possono verificarsi 3 casi
1 - è un nodo di inizio: aggiungo il nodo all'insieme iniziando un nuovo 
cammino. Se sono presenti altre liste, vi aggiungo il nodo
2 - è un nodo di fine: aggiungo il nodo a tutte le liste e le copio nel 
contenitore dei cammini completati
3- è un nodo intermedio: aggiungo solo il nodo a tutti i cammini iniziati
La maggiore complessità dell'algoritmo è data da:
1 - ogni volta che passo ad analizzare un nodo figlio devo copiare 
l'intera struttura di supporto
2 - ogni volta che aggiungo un nodo devo aggiungerlo a tutti i cammini 
iniziati
Esiste un algoritmo più efficiente?

 writes:
diego> Ho realizzato un alogoritmo in java che preso
diego> in input
diego> un albero                        e
diego> un tipo di nodo di partenza A    e
diego> uno di arrivo B
diego> trova tutti i cammini del tipo A--->B
Non precisi cosa intendi per "tipo di nodo", e in seguito proprio
non ne fai piu` accenno. Ma ho dedotto che ne parli in altri termini.
diego> Utilizzo una visita anticipata per visitare l'albero
diego> (complessità n) tramite una procedura ricorsiva
sara` banale, ma bisogna dire che n e` il numero di nodi dell'albero,
altrimenti e` inutile (cioe` non meno banale) citare questa complessita`.
diego> Utilizzo una struttura di supporto che contiene tutti
diego> i cammini iniziati: una insieme di liste che rappresentano i
diego> cammini iniziati fino a quel punto
dubito che sia un "insieme"  (e tantomeno "una insieme"), immagino sia
invece una lista di liste
diego> Uso un contenitore per memorizare i cammini completati
diego> Ad ogni nodo possono verificarsi 3 casi
[durante la visita <nodo padre, alberi figli>, riferendosi a nodo padre]
diego> 1 - è un nodo di inizio: aggiungo il nodo all'insieme iniziando
diego> un nuovo cammino.
[inizio = quello che chiamavi nodo di tipo A]
Quello che chiami insieme e` comunque di liste, quindi aggiungerai/inserirai
una lista contenente un solo elemento corrispondente al nodo (non e` la stessa
cosa che aggiungere un nodo, naturalmente ti si puo` capire, ma ti
segnalo questi errori perche` sono il primo passo che complica
l'immediata semplicita` delle soluzioni, almeno nel mio modo di vedere).
diego> Se sono presenti altre liste, vi aggiungo il nodo
[aggiunto anche a tutte le liste]
diego> 2 - è un nodo di fine: aggiungo il nodo a tutte le liste e le
diego> copio nel contenitore dei cammini completati
Non e` chiero se per "fine" intendi
relativa al percorso A--->B (quindi di tipo B)
o una foglia. Per uniformita` euristica considero che intendi di tipo B.
diego> 3- è un nodo intermedio: aggiungo solo il nodo a tutti i
diego> cammini iniziati
hai comunque scomposto in tre opzioni operazioni con parti in comune,
diego> La maggiore complessità dell'algoritmo è data da:
diego> 1 - ogni volta che passo ad analizzare un nodo figlio devo
diego> copiare l'intera struttura di supporto
diego> 2 - ogni volta che aggiungo un nodo devo aggiungerlo a tutti i
diego> cammini iniziati
diego> Esiste un algoritmo più efficiente?
Premessa: Le strutture dati sono fondamentali, la cui importanza a volte e`
sottovalutata, il tuo sembra essere un problema contorto, vien da
chiedersi perche` hai un albero se poi lo vuoi sbrogliare in liste
prendendone parte dei suoi nodi.
Per "tipo di nodo" A e B intendi che A e B sono due regole che
incontrano un sottoinsieme dei nodi, assumendo che cio` che hai
descritto corrisponde alle tue intenzioni, non avevi precisato
che cerchi il percorso *solo* in senso di discendenza dalla radice
(se si parla di alberi non e` scontato che ci sia una radice,
ed i percorsi in teoria sarebbero come un grafo _non_orientato_
connesso e aciclico, quindi il tuo algoritmo non li troverebbe tutti,
ma trova solo i percorsi di sola discendenza del tipo   tipo A--->tipo B)
tornando alla domanda
diego> Esiste un algoritmo più efficiente?
[che giunga allo stesso contorto risultato]
I principi dell'algoritmo che mi viene in mente sono grossomodo simili:
per ciascun nodo che verifica la regola A  costruirisco una nuova cache
del percorso (sottoforma di lista vincolante).
Non dici come verranno interrogati e usati i dati che costriusci/trasformi.
Immagino che intendessi poter risolvere velocemente la funzione
discendenza: nodo di tipo A, nodo di tipo B |---> percorso obbligato.
Cio` che almeno palesemente non va bene alla base del tuo algoritmo
e` la struttura dati: il dover aggiungere lo stesso nodo a piu` liste
e` evidente segno di inefficienza della struttura dati
(a occhio stimo che mediamente queste liste sono n/4, ipotizzando
 una probabilita` 0.5 che il tipo sia A o B).
Ad ogni nodo di tipo A dovrebbe associarsi la lista di liste
che portano ad ogni nodo discendente di tipo B, eventualmente
attraverso un intermediario di tipo A (che porta a (=/meno)nodi di tipo B),
queste liste partizionano l'insieme dei nodi discendenti di tipo B raggiunti,
l'ideale e` indicizzarle con degli insiemi. [Mi rendo conto che sono
parole insolite, ma da un nodo A interessa risolvere velocemente,
dato un nodo b di tipo B, quale percorso o "tratto successivo di percorso"
scegliere per raggiungerlo, questo percorso e` l'unico ad avere b appartenente
all'insieme di elementi di tipo B raggiunti, da cui l'indicizzazione
con il vero e proprio insieme dei B raggiunti]
es.
                  / b1
             / p2
        / a2
                  / b2
             \ p3
   / p1
        \ a3
a1
        / b3
   \ p4
                  / a4
             / b4
        \ p5
   \ p6
        \ b5
[lascio pensare all'algoritmo che stampa su terminale un albero con
 buona leggibilita`, quindi meglio che nell'esempio precedente]
             / p2 - b1
        / a2
             \ p3 - b2
   / p1
        \ a3
a1
        / b3
   \ p4
        \ p5 - b4 - a4
   \ p6 - b5
comunque
da a1 a b3 c'e` il percorso (a1,p4,b3) indicizzato da {b3}
da a1     a b1 c'e` il percorso parziale (a1,p1,a2)
                       indicizzato da {b1,b2} e in associazione a a2
    da a2 a b1 c'e` il percorso (a2,p2,b1) indicizzato da {b1}
....
Nota: Puo` essere utile che questi percorsi (anche se parziali) specifichino
anche direttamente la cella finale, perche` e` essa che in prima
istanza li contraddistingue.
L'insieme dei nodi di tipo B e` partizionato ad albero gerarchico
(= partizionato ricorsivamente) dove la scelta di (eventuale)
suddivisione e` sui nodi intermedi di tipo A.
L'insieme dei B raggiunti e` da abbinare a ciascun percorso da
un nodo di tipo A al successivo nodo di tipo A o di tipo B stesso.
Il percorso e` terminato se termina su un nodo di tipo B.
Fatte queste premesse,
io risolverei il problema con una lista speciale di visita, tanto che
non serve la ricorsione:
prerequisiti che forse e` il caso di precisare:
  metodo primogenito() e metodo fratello_successivo()
  sulla classe dei nodi dell'albero
parto dalla radice e tengo traccia delle discendenze con una lista(stack)
di stato di visita che ha nodi che si riferiscono ai nodi dell'albero,
risultando una catena di discendenti dalla radice a q (il corrente nodo
visitato)
[ La cima della lista di visita assume i valori da primogenito() a
  tutti i consistenti suoi fratelli successivi, e quando terminano
  si accorcia e si prosegue con il fratello_successivo del padre ]
Lo stato del sistema deve tener traccia dei nodi di tipo A incontrati
lungo la discendenza visitata dalla radice a q.
Questi nodi spezzano eventualmente la lista di visita in segmenti
di percorso contigui, a ciascuno di essi bisogna dire che possono
raggiungere q (attraverso tutti i tratti vincolati univocamente
dalla lista di visita)
Cosicche` se il nodo q e` di tipo B, si salvano in modo permamente
su tutti gli avi di tipo A i percorsi definitivi delle parti della
lista di visita (pronta) che terminano su q(di tipo B).
A seconda di come si interrogheranno i dati,
potra` essere preferibile che le liste di percorso alle destinazioni,
memorizzate in tutti i nodi(estesi) di tipo A, siano indicizzate
con immediatezza proprio dal riferimento delle destinazioni.
Quindi quando si incontra un nodo di tipo B si informano tutti i suoi avi
di tipo A (iterando la diretta lista dinamica di visita), che hanno q come
discendente di tipo B, raggiungibile con immediata e definitiva informazione
solo dal percorso terminante con q nella lista dinamica di visita.
Tutto chiaro?
Saluti,
MARco Munari
-- 
xref: 
http://mar.i.am/~u16658.20485/it.scienza.informatica/albero,it
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14

Esiste un algoritmo più efficiente?
Non ho capito benissimo il procedimento, ma mi sembra un po' diverso
dal mio.
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.