Newsgroup: it.comp.lang.c++
Titolo: cercare percorso in un albero generico

Salve, avendo una classe come la seguente
class node
{
  int nodeID;
  list<node> listOfChildren;
  list<node> listOfParents;
}
Qual'e' il modo piu' furbo/veloce per cercare il padre piu' 'vicino' a due
nodi dati? 
Avevo pensato a Djikstra altre idee?
grazie

 nodi dati?
La soluzione deve essere euristica o esaustiva?
Cioè, vuoi una soluzione ottimale o sub-ottimale?
Ciao.
-- 
---
*************** | Have you ever retired a human by mystake?
*** Azathot *** |
*************** | To contact me, ask me gently. Thanks.

 Cioè, vuoi una soluzione ottimale o sub-ottimale?
soluzione ottima, una sub-ottima si puo' ottenere con un semplice
depth-first ma purtroppo non fa al caso mio...

 depth-first ma purtroppo non fa al caso mio...
Domanda: il padre deve essere "equidistante" dai due nodi in questione, 
oppure il padre "più vicino" ad uno dei due (e, teoricamente, quindi, due 
padri)?


 due padri)?
il piu' vicino e' quello che minimizza il numero di passi da lui ai figli
(passi fino al figlio1 + passi fino al figlio2)

 (passi fino al figlio1 + passi fino al figlio2)
È possibile costruire strutture di supporto per l'esecuzione dell'algoritmo 
o vuoi usare esclusivamente le tue strutture? Inoltre, esistono cicli nella 
rappresentazione?


 
dipende dalle strutture, vorrei mantenere l'algoritmo il piu' snello
possibile (deve girare su macchine datate e si parla di centinaia/migliaia
di nodi)
cicli non ne esistono, nel senso che nessun figlio punta "verso l'alto",
tieni pero' presente che i link padre figlio sono reciproci.

 tieni pero' presente che i link padre figlio sono reciproci.
I vincoli che hai imposto ci dovrebbero aiutare, perché non dobbiamo tener 
"storia" della visita. Io direi di implementare una visita in ampiezza, 
creando una coppia di elenchi di nodi figli (uno per ogni nodo di 
partenza). Ad ogni passo, si espandono gli ultimi figli inseriti per ogni 
elenco. Ci si ferma quando i due insiemi contengono un elemento in comune 
(il padre).
Esempio:
E<-----+--+--+--+
^      |  |  |  |
|      V  V  V  V
|      H  J  F  G
V
D<-----+--+--+
       |  |  |
       V  V  V
       A  B  C
Se ad esempio cerchiamo il padre equidistante tra A e G...
Passo 1:
        lista(A) = A;
        lista(G) = G;
Passo 2:
        lista(A) = A,D;
        lista(G) = G,E;
Passo 3:
        lista(A) = A,D,BC;
        lista(G) = G,E,HJFGD;
L'algoritmo si ferma perché sia lista(A) che lista(G) contengono "D" (che è 
il nodo padre cercato).
Credo che in C++ sia abbastanza facile implementarlo... :)
I miei 2 (euro)cents...


 (il padre).
Non sono sicuro di aver capito (e non ho capito neanche il disegno), ad
esempio in questo caso non mi sembra funzioni:
H ---------> G ---------> F -----------> E -----------> B
|            |
|            |
|            V
|            D
|            |
|            |
|            V
V            C
A <----------|
Vogliamo trovare il padre più vicino ad A e B.
G ha distanza 3+3 = 6
H ha distanza 1+4 = 5
Quindi cerchiamo H e non G.
Con il tuo algoritmo:
Passo 1:
  lista(A) = A
  lista(B) = B
Passo 2:
  lista(A) = A,HC
  lista(B) = B,E
Passo 3:
  lista(A) = A,HC,GD
  lista(B) = B,E,F
Passo 4:
  lista(A) = A,HC,GD,F
  lista(B) = B,E,F,G
G è in comune, H no.
-- 
Marco Barisione
http://spazioinwind.libero.it/marcobari/

 A <----------|
Vediamo:
Passo 1:
        lista(A): A
        lista(B): B
Passo 2:
        lista(A): A,HC
        lista(B): B,E
Passo 3:
        lista(A): AHC,GD
        lista(B): BE,F
Passo 4:
        lista(A): AHCGD,F
        lista(B): BEF,G
Fine dell'algoritmo, il padre più vicino è G. Infatti
|A,G| = 2 
|G,B| = 3
Siccome il grafico è sbilanciato, mi sembra una buona soluzione.
L'altra soluzione poteva essere F (tra l'altro sarebbe persino recuperabile 
se fermassimo l'algoritmo a metà del passo 4). Infatti
|A,F| = 3
|F,B| = 2
In ogni caso, ne cercavamo una.
In cosa è sbagliato l'algoritmo?
Ciao.


 possibile 
Guarda se questo programmino va bene... considera che l'ho compilato e mi da 
i risultati che mi aspetto, però consideralo qualcosa che ho scritto 
sovrappensiero, non l'ho commentato, quindi controllalo e verificalo, e se 
ti servono chiarimenti io sono qui. ;-)
Si compila con
        g++ -O3 -o nev nev.cpp
e si manda in esecuzione con
        ./nev
L'albero che viene costruito nel main( ) è quello dato da Marco Barisione 
nel messaggio <ff6yllr9...@marco.barisione>
Ciao!
--- CUT HERE, FILE: nev.cpp ---
#include <iostream>
#include <list>
#include <set>
#include <algorithm>
#include <string>
#include <stdexcept>
using namespace std;
class Node {
public:
        Node( int _node_id ) : node_id( _node_id ) { };
        int node_id;
        list< Node * > parents;
};
bool operator ==( const Node& _n1, const Node& _n2 ) {
        return _n1.node_id == _n2.node_id;
}
bool operator <( const Node& _n1, const Node& _n2 ) {
        return _n1.node_id < _n2.node_id;
}
Node NearestFather( const set< Node >& _l1, const set< Node >& _l2,
                        const list< Node * >& _s1, const list< Node * >& _s2 ) {
        list< Node * >::const_iterator sit;
#ifdef __DUMP__ALGORITHM__
        static int step = 0;
        ++step;
        cout << "[" << step << "] _l1 = {";
        set< Node >::const_iterator cit;
        for( cit = _l1.begin(); cit != _l1.end(); ++cit )
                cout << (char) (*cit).node_id << " ";
        cout << "}" << endl;
        cout << "[" << step << "] _l2 = {";
        for( cit = _l2.begin(); cit != _l2.end(); ++cit )
                cout << (char) (*cit).node_id << " ";
        cout << "}" << endl;
#endif
        if ( _s1.size() == 0 && _s1.size() == 0 )
                throw( new runtime_error( "Terminals are disjointed!" ) );
        set< Node > l1( _l1 );
        for( sit = _s1.begin(); sit != _s1.end(); ++sit )
                l1.insert( *(*sit) );
        set< Node > l2( _l2 );
        for( sit = _s2.begin(); sit != _s2.end(); ++sit )
                l2.insert( *(*sit) );
        set< Node > fathers;
        insert_iterator< set< Node > > fathers_iterator( 
                fathers, 
                fathers.begin() );
        set_intersection( l1.begin(), l1.end(), 
                l2.begin(), l2.end(), 
                fathers_iterator );
        if ( fathers.size() == 0 ) {
                list< Node * > as1;
                list< Node * >::const_iterator asit1;
                for( asit1 = _s1.begin(); asit1 != _s1.end(); ++asit1 )
                        as1.insert( as1.begin(), 
                                (*asit1)->parents.begin(), 
                                (*asit1)->parents.end() );
                list< Node * > as2;
                list< Node * >::const_iterator asit2;
                for( asit2 = _s2.begin(); asit2 != _s2.end(); ++asit2 )
                        as2.insert( as2.begin(), 
                                (*asit2)->parents.begin(), 
                                (*asit2)->parents.end() );
                return NearestFather( l1, l2, as1, as2 );
        }
        return *fathers.begin( );
}
Node NearestFather( const Node& _n1, const Node& _n2 ) {
        set< Node > a, b;
        list< Node > empty;
        a.insert( _n1 );
        b.insert( _n2 );
        return NearestFather( a, b, _n1.parents, _n2.parents );
}
int main( ) {
        Node a( 'a' ), b( 'b' ), c( 'c' ), 
                d( 'd' ), e( 'e' ), f( 'f' ), 
                g( 'g' ), h( 'h' );
        a.parents.push_back( &c );
        a.parents.push_back( &h );
        b.parents.push_back( &e );
        c.parents.push_back( &a );
        c.parents.push_back( &d );
        d.parents.push_back( &g );
        d.parents.push_back( &c );
        e.parents.push_back( &f );
        e.parents.push_back( &b );
        f.parents.push_back( &g );
        f.parents.push_back( &e );
        g.parents.push_back( &h );
        g.parents.push_back( &f );
        h.parents.push_back( &a );
        h.parents.push_back( &g );
        try {
                cout << (char) NearestFather( a, b ).node_id << endl;
        } catch( runtime_error * _e ) {
                cerr << _e->what() << endl;
                delete _e;
        } catch( ... ) {
                cerr << "Internal error" << endl;
        }
        return 0;
}
--- CUT HERE --- --- CUT HERE --- --- CUT HERE ---


 
Addendum al programma di cui sopra. Questo è il "main" per ciò che attiene 
questo esempio:
--- CUT HERE --- --- CUT HERE --- --- CUT HERE ---
[omissis]
int main( ) {
        Node a( 'a' ), b( 'b' ), c( 'c' ), d( 'd' ),
                e( 'e' ), f( 'f' ), g( 'g' ), h( 'h' ),
                j( 'j' );
        a.parents.push_back( &d );
        b.parents.push_back( &d );
        c.parents.push_back( &d );
        d.parents.push_back( &a );
        d.parents.push_back( &b );
        d.parents.push_back( &c );
        d.parents.push_back( &e );
        e.parents.push_back( &d );
        e.parents.push_back( &f );
        e.parents.push_back( &g );
        e.parents.push_back( &h );
        e.parents.push_back( &j );
        f.parents.push_back( &e );
        g.parents.push_back( &e );
        h.parents.push_back( &e );
        j.parents.push_back( &e );
        try {
                cout << (char) NearestFather( a, g ).node_id << endl;
        } catch( runtime_error * _e ) {
                cerr << _e->what() << endl;
                delete _e;
        } catch( ... ) {
                cerr << "Internal error" << endl;
        }
        return 0;
};
--- CUT HERE --- --- CUT HERE --- --- CUT HERE ---
-- 


 ti servono chiarimenti io sono qui. ;-)
ti ringrazio dell'aiuto e del tempo dedicatomi :-)
purtroppo ho letto soltanto adesso i tuoi messaggi e ho gia' trovato una
via che funziona, la espongo cosi' magari puoi 'smontarla' :-)
In realta' pero' confesso che non avevo detto tutta la verita'... c'era
qualche altro vincolo che avevo dimenticato...
i nodi posseggono un certo "livello" (membro della classe) che sara', come
minimo, uguale al livello del 'padre-con-livello-massimo' +1 ma che
potrebbe anche essere piu' alto. Quindi il padre + vicino e' quello con
livello + alto.
Con questo nuovo vincolo nel caso dell'albero proposto da Marco (grazie
anche a te :-) ) la soluzione ottimale risulta G e non H.
Quello che ho fatto e' (credo) molto simile a quello che hai fatto tu...
ovvero una ricerca breadth-first a partire dai due nodi in questione fino
ad arrivare alla radice. In tal modo trovo _tutti_ i nodi possibili per
giungere a quei nodi (singolarmente) dopodiche' una intersezione delle due
liste mi fornisce i padri comuni tra i quali scelgo quello di livello
massimo.
Considerando anche il fattore 'livello' e' sicuro che il primo incontrato
(che hai usato come terminazione della ricerca) sia una soluzione ottima?
a occhio sembra di si' (e mi risparmierei parecchi confronti inutili) ma
data l'ora credo che controllero' domani :-)
grazie ancora e buon ferragosto :-)  

 (che hai usato come terminazione della ricerca) sia una soluzione ottima?
Con il discorso "livello" non lo so. Senza sicuramente sì. Infatti, sia
        lista(A) = AX,Y
        lista(B) = BZ,Y
Se Y è una soluzione, essa è anche ottima[1]. Se per assurdo non lo fosse, 
vorrebbe dire che esiste un elemento K tale per cui
|A,K| < |A,Y|
|K,B| < |Y,B|
Ma se K esiste, doveva essere stato coperto dall'algoritmo prima di Y, 
perché significava che il numero di passi per arrivarci era inferiore. 
Assurdo!
Ciao e buon ferragosto!
-- 
[1] Non necessariamente unica, però!
