Algoritmo Divide-And-Conquer per gli alberi

Question

Sto provando a scrivere un divario & algoritmo di conquista per gli alberi. Per il passaggio divide ho bisogno di un algoritmo che partizioni un dato G indirizzato (V, E) con n nodi e m bordi in sottoalberi rimuovendo un nodo . Tutti i sottografi devono avere la proprietà che non contengano più di n/2 nodi (l'albero deve essere diviso il più uguale possibile). Per prima cosa ho provato a rimuovere ricorsivamente tutte le foglie dall'albero per trovare l'ultimo nodo rimasto, quindi ho cercato di trovare il percorso più lungo in G e rimuovere il nodo centrale di esso. La data grafico sottostante mostra che entrambi gli approcci non funzionano:

C'è qualche algoritmo di lavoro che fa quello che voglio (restituisce il nodo H nel caso di cui sopra).

Answer 1

Penso che si potrebbe fare con un algoritmo simile a questo:

Start nella root (se l'albero non è radicato, scegliere qualsiasi nodo).
In ogni passaggio, provare a discendere nel nodo figlio con la sottostruttura più grande (il numero di nodi "sotto" è il più grande).
Se ciò dovesse fare il numero di nodi "sopra" maggiore di n/2, fermarsi, altrimenti continuare con quel bambino.

Questo algoritmo deve essere O (log n) se l'albero è ragionevolmente bilanciato e abbiamo dimensioni di sottostrutture precalcolate per ciascun nodo. Se una di queste condizioni non si applica, sarebbe O (n).

Answer 2

Un algoritmo esatto è il presente,

Inizio dalle foglie e creare grafici disgiunti (in realtà tutti sono K1), in ogni passaggio trovare il padre di questo foglie, e fonderli in nuovo albero, in ogni passaggio se il nodo x ha r bambino conosciuto e il grado di nodo è j tale che j = r+1, semplicemente un nodo che non è in nodo figlio x è madre di nodo corrente in questo caso si dice nodo x è nice, altrimenti, ci sono alcuni di questi bambini quella relativa sottostruttura radice di loro non costruita, in questo caso diciamo che il nodo x è bad.

Quindi, in ogni fase connettersi nice nodi al loro genitore correlate, ed è evidente ogni passaggio richiede sum of {degree of parent nice nodes} anche in ogni passo di avere almeno un bel nodo (causa si inizia da foglia), Quindi l'algoritmo è O (n) , e sarà fatto completamente, ma per trovare il nodo che dovrebbe essere rimosso, infatti in ogni passaggio è richiesto di controllare la dimensione di una lista dijoint (liste di sottostrutture), questo può essere fatto in O (1) nella costruzione, anche se la dimensione della lista è uguale o superiore a n/2, quindi seleziona il nodo bello correlato. (in effetti trova il nodo simpatico nella lista minima che soddisfa questa condizione).

La cosa ovvia è che se è possibile dividere l'albero in modo corretto (ogni parte ha al massimo n/2 nodi) è possibile farlo con questo algoritmo, ma se non lo è (in effetti non puoi dividerlo in due o più parti di dimensioni inferiori a n/2) questo ti dà una buona approssimazione per questo. Inoltre, come puoi vedere, non c'è ipotesi nella struttura di input.

nota: non so è possibile avere un albero tale che è impossibile dividerlo in alcune parti di dimensioni inferiori a n/2 rimuovendo un nodo.

Answer 3

Questo problema sembra simile alla ricerca dello center of mass di un oggetto. Supponiamo che ognuno dei tuoi nodi sia una massa puntiforme di uguale massa (peso) e che la sua posizione sia data dalla posizione nel grafico. Il tuo algoritmo prova a trovare il centro di massa, cioè il nodo che ha un peso accumulato simile di nodi in tutti i sub-alberi connessi.

È possibile calcolare i pesi accumulati su tutti i sotto-alberi per ciascun nodo. Quindi scegli quello più equilibrato, ad es. nessun sotto-albero pesa più di n/2. Probabilmente questo è un compito per alcune programmazioni dinamiche.