Ho una domanda che fa parte del mio programma.Trovare il centro dell'albero
Per un albero T = (V, E) è necessario trovare il nodo v nell'albero che riduca al minimo la lunghezza del percorso più lungo da v a qualsiasi altro nodo.
così come troviamo il centro dell'albero? C'è un solo centro o più?
Se qualcuno può darmi un buon algoritmo per questo, così posso avere l'idea di come posso inserirmi nel mio programma.
Si consideri un albero con due nodi? Qual è il centro? O uno sarà sufficiente, ergo un albero può avere più di un centro.
Ora, pensa a cosa significa essere il centro. Se tutti i rami hanno la stessa altezza, il centro è la radice (tutti i percorsi passano attraverso la radice). Se i rami sono di altezze diverse allora il centro deve essere o la radice o nel ramo con l'altezza massima altrimenti il percorso massimo è maggiore dell'altezza del ramo più alto e la radice sarebbe una scelta migliore. Ora, quanto dobbiamo cercare nel ramo più alto? Metà della differenza di altezza tra il ramo più alto (dalla radice) e il ramo più alto successivo (se la differenza è al massimo 1, la radice sarà sufficiente). Perché, poiché mentre scendiamo il ramo più alto di un livello, stiamo allungando di uno il percorso verso il nodo più profondo del prossimo ramo più alto e riducendo di uno la distanza dal nodo più profondo del ramo corrente. Alla fine, saranno uguali quando avrai attraversato metà della differenza nella profondità. Ora mentre scendiamo nel ramo più alto, abbiamo semplicemente bisogno di scegliere ad ogni livello il ramo secondario più alto. Se più di uno ha la stessa altezza, ne scegliamo semplicemente uno arbitrariamente.
In sostanza, ciò che si sta facendo è trovare il percorso più lungo nel grafico, che è la distanza tra il ramo più alto dell'albero e il successivo ramo più alto, quindi trovare il nodo centrale su quel ramo. Poiché potrebbero esserci più percorsi della stessa lunghezza del percorso più lungo e la lunghezza del percorso più lungo potrebbe essere pari, sono disponibili più centri possibili.
Piuttosto che fare questo problema i compiti per te, ho intenzione di chiedere l'utente attraverso il processo di pensiero che ottiene la risposta ...
1) Cosa faresti con l'abc grafico (a tre vertici, due bordi e decisamente aciclici)? Immagina per un momento che devi mettere alcune etichette su alcuni dei vertici, sai che otterrai il minimo del percorso più lungo sul vertice "centrale". (b, con l'eventuale etichetta "1") Ma farlo in un solo passo richiede poteri psichici. Quindi chiediti cosa è a 1 passo da. Se il percorso più lungo per b è 1, e abbiamo appena fatto un passo indietro lungo quel percorso, qual è la lunghezza del nostro percorso finora? (percorso più lungo = 1, -1 per il gradino posteriore. Aha: 0). Quindi deve essere l'etichetta per le foglie.
2) Cosa suggerisce questo come primo taglio per un algoritmo? Segna le foglie "0", segna i loro upstream "1", segna i loro upstream "2" e così via. Marciamoci dalle foglie e contando la distanza mentre andiamo ...
3) Umm ... Abbiamo un problema con il grafico a-b-c-d. (D'ora in poi, un vertice etichettato verrà sostituito con la sua etichetta.) Etichettare le foglie "0" dà 0-bc-0 ... Non possiamo ottenere due centri ... diamine, che cosa facciamo nel più semplice condizione 0-b-1? Vogliamo etichettare b con entrambi "1" e "2" ... Gestire quelli in ordine inverso ...
In 0-b-1, se estendiamo il percorso da sinistra a sinistra di uno, otteniamo un percorso di lunghezza 1. Se estendiamo il percorso da b a destra, otteniamo 2. Vogliamo tracciare "la lunghezza del percorso più lungo da v a qualsiasi altro nodo", quindi vogliamo tenere traccia del percorso più lungo verso b. Ciò significa che contrassegniamo b con un "2".
0-b-1 -> 0-2-1
In 0-b-c-0, il computer non fa effettivamente simultaneamente b aggiornamento e c. Aggiorna uno di loro, dando 0-1-c-0 o 0-b-1-0, e il prossimo aggiornamento dà 0-1-2-0 o 0-2-1-0. Sia b che c sono "centri" di questo grafico poiché ognuno di essi soddisfa la domanda "il nodo v nell'albero che minimizza la lunghezza del percorso più lungo da v a qualsiasi altro nodo". (La lunghezza è 2.)
Questo porta a un'altra osservazione: il risultato del calcolo non è quello di etichettare un grafico, è quello di trovare l'ultimo vertice che etichettiamo e/o il vertice che finisce con l'etichetta più grande. (È possibile che non troveremo un buon modo per ordinare le etichette, quindi finiremo per dover trovare il massimo alla fine, o forse lo faremo. Chissà.)
4) Quindi ora abbiamo qualcosa come: Crea due copie del grafico: la copia etichettata e la copia di burn-down. Il primo memorizzerà le etichette ed è quello che avrà la risposta finale. La copia burn-down diventerà sempre più piccola man mano che eliminiamo i vertici non etichettati (per trovare nuovi vertici etichettabili). (Ci sono altri modi per organizzare questo in modo che solo una copia del grafico viene utilizzata quando si arriva alla fine di comprendere questa risposta, si dovrebbe trovare un modo per ridurre questo spreco..) Outline:
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
5) Se guardi effettivamente questa corsa, noterai diverse opportunità per la scorciatoia. Compresa la sostituzione della ricerca sull'ultima riga del contorno con un metodo molto più rapido per riconoscere la risposta.
E ora per suggerimenti di strategia generale per problemi con l'algoritmo:
* Fai alcuni piccoli esempi a mano. Se non capisci come fare i casi piccoli, non c'è modo di entrare direttamente e dire al computer come fare i casi più grandi. * Se uno qualsiasi dei passaggi precedenti sembrava immotivato o totalmente opaco, è necessario studiare molto, molto più difficile da fare bene in Informatica. Può essere l'informatica non è per voi ...
Ci sono due approcci per fare questo (sia eseguito nello stesso tempo):
Selezionare qualsiasi vertice v1 sul vostro albero. Esegui BFS da questo vertice. L'ultimo vertice (v2) che procederai sarà il vertice più lontano da v1. Ora esegui un altro BFS, questa volta dal vertice v2 e ottieni l'ultimo vertice v3.
Il percorso da v2 a v3 è il diametro dell'albero e il centro si trova da qualche parte su di esso. Più precisamente si trova nel mezzo di esso. Se il percorso ha punti 2n + 1, ci sarà solo 1 centro (nella posizione n + 1). Se il percorso ha punti 2n, ci saranno due centri nelle posizioni n e n + 1.
Si utilizzano solo 2 chiamate BFS che vengono eseguite nel tempo 2 * O(V).
Se il punto centrale esattamente non esiste, come potremmo scegliere? Voglio dire, se il modo più lungo è a-b-c, a-b ha lunghezza 1 e b-c ha lunghezza 2?O un esempio più complesso? – cnhk
Scegline uno arbitrariamente, se hai semplicemente bisogno di un nodo che si qualifica, o costruisci un set centrale, se hai bisogno di tutto ciò che si qualifica. – tvanfosson