[Algoritmi, Problema] Selezione casuale di Nodi in un albero
Si ha un albero i cui nodi possono avere un numero variabile di ramificazioni.
La classe della struttura è definita in tal modo (c++):
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.
La classe della struttura è definita in tal modo (c++):
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.
Risposte
Conosci la funzione rand()?
"Flamber":
Conosci la funzione rand()?
certo... ma da sola serve a ben poco in questo caso.
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?
* Immagino che tu sappia come scegliere all'interno di una partizione di un insieme sapendo la probabilità di ogni sottoinsieme?
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
"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
L'implementazione della classe deve essere quella che ho specificato.
Comunque in che senso "per ogni nodo"? Non deve essere O(n)
"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*.
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à...
"apatriarca":
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.
"apatriarca":
È 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)).
"lorenzom97":
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.
"lorenzom97":
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.
'"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)).
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)\)..
"apatriarca":
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.
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.
"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.
E' possibile. Pensa bene al significato di "reale probabilità"...
La probabilità di un sottoalbero \(S\) è ovviamente \(|S|/N\) dove \(|S|\) è il numero di nodi del sottoalbero ed \(N\) il numero di nodi dell'albero. Ma non c'è modo di conoscere il numero di nodi del sottoalbero a meno di contarli (e questo richiede una complessità \(O(n)\)..
"apatriarca":
La probabilità di un sottoalbero \(S\) è ovviamente \(|S|/N\) dove \(|S|\) è il numero di nodi del sottoalbero ed \(N\) il numero di nodi dell'albero. Ma non c'è modo di conoscere il numero di nodi del sottoalbero a meno di contarli (e questo richiede una complessità \(O(n)\)..
Non ti devi concentrare sulla probabilità di un sottoalbero, ma sulla probabilità dei singoli nodi (che tu conosci, 1/N).
Non vedo come questa probabilità possa essere usata per scegliere su quale sottoalbero continuare la ricorsione.. Sei sicuro che la complessità del tuo metodo sia effettivamente O(\log N\)?
"apatriarca":
Non vedo come questa probabilità possa essere usata per scegliere su quale sottoalbero continuare la ricorsione.. Sei sicuro che la complessità del tuo metodo sia effettivamente O(\log N\)?
Si, sono sicuro. Altro aiuto: la scelta del sottoalbero è causale.
Aiuto: guardare l'ultima modifica al mio post iniziale (non cambia niente del problema, ma per alcune implementazioni potrebbe essere utile).
La scelta del sottoalbero è necessariamente casuale. Qualsiasi metodo venga scelto, avrai infatti bisogno di prendere una strada a scelta tra quelle presentate. Suppongo tu stia quindi dicendo che un sottoalbero viene scelto a caso con probabilità uniforme? In questo caso stai allora sopra- o sotto- stimando la probabilità di scegliere un nodo da uno specifico sottoalbero. Considera per esempio il caso in cui la radice abbia due sottoalberi (uno con \(1\) solo nodo e l'altro con \(N-2\) nodi..). Continuo insomma a non vedere come sia sufficiente usare \(1/N\) senza passare ad una complessità maggiore o aggiungere altri dati al nodo.
"apatriarca":
La scelta del sottoalbero è necessariamente casuale. Qualsiasi metodo venga scelto, avrai infatti bisogno di prendere una strada a scelta tra quelle presentate. Suppongo tu stia quindi dicendo che un sottoalbero viene scelto a caso con probabilità uniforme? In questo caso stai allora sopra- o sotto- stimando la probabilità di scegliere un nodo da uno specifico sottoalbero. Considera per esempio il caso in cui la radice abbia due sottoalberi (uno con \(1\) solo nodo e l'altro con \(N-2\) nodi..). Continuo insomma a non vedere come sia sufficiente usare \(1/N\) senza passare ad una complessità maggiore o aggiungere altri dati al nodo.
Quello che ho detto significa che il sottoalbero va scelto con probabilità uniforme (casualmente) per proseguire, non per essere scelto.
Ma se l'algoritmo visita più di un sottoalbero.. come fai a mantenere la complessità uguale all'altezza dell'albero? Stiamo parlando di complessità media?
"apatriarca":
Ma se l'algoritmo visita più di un sottoalbero.. come fai a mantenere la complessità uguale all'altezza dell'albero? Stiamo parlando di complessità media?
Esatto. La complessità media dell'algoritmo è uguale all'altezza media dell'albero
Chiedo scusa a tutti quelli che si sono cimentati a risolvere questo problema.
Trasportato dall'entusiasmo, vi ho posto questo problema, senza effettuare i dovuti test. La soluzione che pensavo di aver trovato funziona per alberi piccoli, ma per alberi un pò più grandi mostra anomalie ed errori, che inizialmente non avevo riscontrato.
Lascio aperta la questione nel caso lo risolvessi (una volta per tutte
) o qualcun altro lo risolvesse.
Scusatemi ancora
Trasportato dall'entusiasmo, vi ho posto questo problema, senza effettuare i dovuti test. La soluzione che pensavo di aver trovato funziona per alberi piccoli, ma per alberi un pò più grandi mostra anomalie ed errori, che inizialmente non avevo riscontrato.
Lascio aperta la questione nel caso lo risolvessi (una volta per tutte
) o qualcun altro lo risolvesse.Scusatemi ancora
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo