[Algoritmi, Problema] Selezione casuale di Nodi in un albero

[lorenzom97]

Si ha un albero i cui nodi possono avere un numero variabile di ramificazioni.
La classe della struttura è definita in tal modo (c++):

Codice:

class Node
{
public:

      Node();
      ~Node();

private:
     
     vector<Node*> NextNodes;    //Numero variabile di figli diretti
};


Definire un algoritmo che non sia O(n), che, partendo dal Root (Nodo Primario), arrivi a selezionare casualmente un Nodo all'interno dell'albero, in modo che la distribuzione della probabilità (che un nodo sia scelto) sia uniforme in tutto l'albero (la probabilità totale di essere selezionato deve essere uguale per tutti i nodi), conoscendo unicamente il numero totale di nodi all'interno dell'albero. ( Naturalmente però un nodo conosce il numero dei figli diretti )

Il problema, così come è descritto, è irrisolvibile, come dimostrato da vict85.

[Flamber]

Conosci la funzione rand()?

[lorenzom97]

Conosci la funzione rand()?

certo... ma da sola serve a ben poco in questo caso.

[apatriarca]

Supponiamo di avere una versione più semplice, in cui ogni nodo memorizza il numero di figli. Conoscendo questo dato si può calcolare la probabilità di ogni sottoalbero e quindi agire di conseguenza*. Senza conoscere questo dato il problema non mi sembra invece facilmente risolvibile. Sicuramente è possibile scrivere un algoritmo che opera la scelta in modo che la probabilità sia mediamente (nel senso che lo è prendendo tutti gli alberi casuali con un certo numero di nodi) quella desiderata. È infatti sufficiente scegliere in modo uniforme tra gli N sottoalberi di quello preso in considerazione. Dove hai preso il problema? Era presentato in questo modo?

* Immagino che tu sappia come scegliere all'interno di una partizione di un insieme sapendo la probabilità di ogni sottoinsieme?

[Flamber]

Ogni nodo punta ai suoi figli che avrai etichettato in qualche maniera, oltre ai figli potresti inserire una sequenza di uscita per ogni nodo, e scegliere casualmente tra uno dei figli o la sequenza di uscita, che restituisca il nodo a cui è arrivata la scansione. Questo chiaramente per ogni nodo

[lorenzom97]

Ogni nodo punta ai suoi figli che avrai etichettato in qualche maniera, oltre ai figli potresti inserire una sequenza di uscita per ogni nodo, e scegliere casualmente tra uno dei figli o la sequenza di uscita, che restituisca il nodo a cui è arrivata la scansione. Questo chiaramente per ogni nodo

L'implementazione della classe deve essere quella che ho specificato.
Comunque in che senso "per ogni nodo"? Non deve essere O(n)

[lorenzom97]

Supponiamo di avere una versione più semplice, in cui ogni nodo memorizza il numero di figli. Conoscendo questo dato si può calcolare la probabilità di ogni sottoalbero e quindi agire di conseguenza*.

Intendi il numero ti tutti i figli, anche i figli indiretti ( i figli dei figli etc.)? Anche se fosse, non servirebbe calcolare alcun tipo di probabilità...

Sicuramente è possibile scrivere un algoritmo che opera la scelta in modo che la probabilità sia mediamente (nel senso che lo è prendendo tutti gli alberi casuali con un certo numero di nodi) quella desiderata.

L'algoritmo deve garantire che la probabilità sia uniforme in ogni singolo albero. Non "mediamente" uniforme.

È infatti sufficiente scegliere in modo uniforme tra gli N sottoalberi di quello preso in considerazione. Dove hai preso il problema? Era presentato in questo modo?

Non è sufficiente. Comunque il problema originale era un problema che Google sottoponeva ai contendenti per il lavoro, ma era più facile ( dava carta bianca su come implementare la classe e non specificava che l'algoritmo non deve essere O(n)).

[apatriarca]

Intendi il numero ti tutti i figli, anche i figli indiretti ( i figli dei figli etc.)? Anche se fosse, non servirebbe calcolare alcun tipo di probabilità...

Esatto. In questo caso la probabilità di scegliere un nodo tra gli alberi figli è uguale al numero di nodi all'interno del sottoalbero corrispondente diviso il numero di nodi dell'albero con radice nel nodo corrente. Si può quindi partire dalla radice e scegliere tra restituire il nodo corrente oppure continuare in modo ricorsivo su uno dei nodi figli in base alla probabilità di ognuno calcolata come ho descritto prima. Questo algoritmo ha ovviamente complessità uguale all'altezza dell'albero.

Non è sufficiente.

Infatti non era una soluzione al problema.. Solo una osservazione su come il discorso della probabilità potesse avere interpretazioni diverse. Ma non ha importanza.

[quote='"lorenzom97"]Comunque il problema originale era un problema che Google sottoponeva ai contendenti per il lavoro, ma era più facile (dava carta bianca su come implementare la classe e non specificava che l'algoritmo non deve essere O(n)).[/quote]
Suppongo quindi che tu disponga di una soluzione al problema dato. Ma hai cambiato la richiesta da complessità logaritmica a complessità diversa da \(O(n)\)? La prima volta che ho letto il tuo problema mi sembrava ci fosse scritto che la complessità dovesse essere \(O(\log n)\)..

[lorenzom97]

Suppongo quindi che tu disponga di una soluzione al problema dato. Ma hai cambiato la richiesta da complessità logaritmica a complessità diversa da \(O(n)\)? La prima volta che ho letto il tuo problema mi sembrava ci fosse scritto che la complessità dovesse essere \(O(\log n)\)..

Si, ho una soluzione. Comunque ho cambiato la descrizione del problema in quanto non so molto di complessità computazione, e non sapevo se la mia soluzione fosse realmente O(logn), ma sicuramente non è O(n).
Il mio algoritmo ha (come hai detto te in un post precedente) una complessità massima uguale all' altezza massima dell'albero, non so come tradurlo in simboli matematici.

[apatriarca]

L'altezza media di un albero come quello che hai descritto dovrebbe essere \(\log_m n\) dove \(m\) è il numero medio di figli di un nodo. Ma per avere una complessità del genere è necessario poter scegliere tra i diversi nodi figli in base alla loro reale probabilità che non vedo come possa essere calcolata senza conoscere il numero totale di ogni sottoalbero figlio.