La tua soluzione sembra cercare di affrontare il tempo di lettura medio dei nodi e tutti i percorsi da essi. Ovviamente, funzionerà, a condizione che sia implementato correttamente.
Il problema con questo approccio è che le quantità calcolate non sono riutilizzabili. Il tempo medio di lettura di un nodo dipende da come ci si arriva. Da qui il comportamento quadratico della tua soluzione ingenua. Il primo passo per cercare di ottimizzarlo è cercare di trovare i risultati dei calcoli riutilizzabili .
Uno di questi potenziali risultati è il costo di prendere un collegamento o qual è il tempo di lettura previsto dopo essere passati dalla domanda A alla domanda B? . Qual è la differenza tra un "nodo" e un "link"? Un 'link' ha sia una destinazione che una origine . Poiché esiste esattamente 1 percorso tra due nodi qualsiasi e non è possibile ripetere i nodi nella lettura, una volta preso un collegamento, qualsiasi nodo raggiungibile attraverso l'origine è ora inaccessibile. Quindi non importa quale percorso hai preso prima del link . Quindi questa quantità è riutilizzabile.
Quindi dobbiamo rispondere a 2 domande:
- Aiuta?
- Quanto velocemente possiamo calcolare questa quantità?
La prima domanda è facile: se abbiamo i costi di prendere i collegamenti, è estremamente facile trovare i tempi medi di lettura quando viene dato un nodo iniziale - è solo il tempo del nodo + la media dei collegamenti in uscita. Di conseguenza, dato che possiamo ottenere la risposta in una singola ricerca lineare.
La seconda domanda è leggermente più difficile - come si calcolano i costi legati all'assunzione di collegamenti in modo (relativamente) efficace?
È abbastanza semplice se ci pensi.
- Il costo di prendere un nodo foglia è solo il tempo di lettura previsto della foglia.
- Il costo del collegamento a un nodo è il tempo di lettura del nodo più la media tra tutti i link in uscita da quel nodo tranne il link inverso .
Questo è un metodo. Quanto è buono? In realtà è lineare! Se prendiamo l'albero dato (e prendiamo il nodo any come root), possiamo calcolare i costi di prendere i collegamenti verso il basso in una semplice scansione lineare (dato che non possiamo prendere un link verso l'alto dopo averne uno verso il basso ). Dopo che avremo tutti i costi dei collegamenti verso il basso, possiamo eseguire una seconda scansione lineare dall'alto verso il basso per calcolare i collegamenti verso l'alto.
Quindi dato che puoi ottenere connessioni di un nodo in tempo costante, l'intera operazione è di soli 3 movimenti lineari!
Poiché apparentemente c'è un po 'di confusione su come funziona, un passo dopo l'input di esempio sul sito web:
Abbiamo 5 nodi connessi in una catena con i pesi 2, 2, 1, 2, 2:
O - O - O - O - O
2 2 1 2 2
Prendi, ad esempio, il secondo nodo come root per la procedura. Una seconda variante a destra avrà il terzo nodo come radice per il confronto:
O O
/ \ / \
O O O O
| | |
O O O
|
O
Calcola il costo dei link in discesa (a destra del link):
O O
/2 /4
O O O O
|4 |2 |2
O O O
|2
O
Ora calcola i link verso l'alto (a sinistra del link):
O O
7/2 4 5/4 5
O O O O
5|4 7|2 7|2
O O O
7|2
O
Nota che i risultati sono gli stessi! (Come nei costi di collegamento, non negli alberi).
Ora genera tempo di lettura medio da questi dati (ora del nodo + link sinistro + link destro):
Node 1: 2 + 0 + 7 = 9
Node 2: 2 + 2/2 + 5/2 = 5.5
Node 3: 1 + 4/2 + 4/2 = 5
Node 4: 2 + 5/2 + 2/2 = 5.5
Node 5: 2 + 7 + 0 = 9
Quindi il nodo con tempo di lettura minimo previsto è il Nodo 3!