Un'azienda vi pone il seguente insensato problema. Il personale è costituito da N persone organizzate gerarchicamente secondo un albero di dipendenze. Ogni persona dell'azienda corrisponde ad un nodo dell'albero e tutti i suoi dipendenti stanno nel sottoalbero radicato nel nodo corrispondente. Sulle foglie vi sono gli impiegati che dirigono solo se stesse ed alla radice c'è il direttore megagalattico.
Il problema è questo: dovete assegnare ad ogni persona dell'azienda un' etichetta consistente di O(log N) bits in maniera tale che quando due tizi si incontrano allora guardando solamente le loro etichette possono determinare se e chi di loro è dipendente dell'altro o se nessuno dei due lo è.
Se non esistono persone con un solo dipendente, si può fare così.
Si modifica l'albero delle dipendenze in modo che diventi un albero binario, aggiungendo O(n) nodi.
Il grande capo riceve l'etichetta vuota.
Ogni volta che un nodo riceve un'etichetta, va dai suoi 2 figli e copia la sua etichetta sulla loro, aggiungendo uno 0 e un 1 alla fine, rispettivamente.
A è dipendente di B se e solo se l'etichetta di B è un prefisso di quella di A.
Nel caso generale, si può provare a "contrarre" in un solo nodo le catene di nodi con un solo figlio, e codificare in binario la posizione nella catena (la contrazione va fatta prima di estendere l'albero per farlo diventare binario).
Poi si codificano le etichette nello stesso modo, ma aggiungendo un bit di controllo per ogni bit, ottenendo una stringa finale della forma 0x0x0x0x1yyyy (proprio volendo sprecare spazio...). Il numero xxxx codifica come prima la posizione nell'albero contratto, mentre il numero yyyy codifica la posizione nell'eventuale catena relativa al nodo dell'albero contratto.
A è dipendente di B se e solo se la parte di etichetta xxxx di B è un prefisso stretto di quella di A, oppure se le xxxx sono uguali, ed il numero yyyy di A è maggiore di quello di B.
Così dovrebbe funzionare, dimmi se va bene. La dimostrazione che la 2^ codifica occupa O(log n) bit è banale...
Io ho pensato a questa soluzione: a ogni membro dell'azienda si dà un numero identificativo calcolato col preordine partendo dal megacapo. Per esempio:
main() {
assegna(nodo_principale);
}
assegna(nodo x) {
identificativo(x); \\assegna come identificativo il primo numero disponibile al nodo x
for (y: figlio di x) {
assegna(y);
}
}
L'etichetta di ogni lavoratore consiste in una coppia di numeri formata dall'identificativo e dal valore massimo raggiunto dagli identificativi dei sottoposti del lavoratore in questione (in pratica, dal valore massimo nel sottoalbero).
L'etichetta così formata è ancora O(log N).
Un lavoratore sa di essere un sottoposto di un altro se e solo se il suo identificativo è compreso tra i due valori dell'etichetta dell'altro.
Rand, è questa la soluzione semplice che avevi in mente ?
@Ippparco: In effetti si, avevo in mente la soluzione che hai descritto informalmente. Ogni persona prende come etichetta una coppia di interi in [N] che sono semplicemente il tempo di inizio e il tempo di fine visita del nodo corrispondente in una visita in profondità dell'albero. L'etichetta ha 2 log N bit.
@MindFlyer: Se si può ridurre dunque il problema al caso in cui l'albero è binario e anche bilanciato allora la tecnica che hai descritto lo risolve. Ma è la riduzione che non mi sembra così banale: aggiungendo O(n) nodi puoi far diventare l'albero binario ma come fai a garantire che sia anche bilanciato?
Ok, ho capito il senso di "primo numero disponibile" della soluzione di Ipparco.
@rand: hai ragione, davo per scontato che l'albero che viene fuori fosse bilanciato, ma non è necessariamente così. Forse riuscirei a "salvare la situazione" con qualche trasformazione+relativa codifica, ma vista la soluzione di Ipparco sarebbe fatica sprecata.
).
