7

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:Algoritmo Divide-And-Conquer per gli alberi

Graph

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

+1

Non capisco, se rimuovi 'H' ottieni 9 sottoalberi! – Shahbaz

+0

Sì, mi dispiace per non essere chiaro qui, posso ottenere molti sottoalberi ma non voglio che uno sia più grande della metà del grafico per assicurare che eseguo solo un conteggio logaritmico dei passaggi di divisione. – Listing

+0

Un'altra cosa, come si mette "l'albero dovrebbe essere diviso il più uguale possibile" in un valore computabile? – Shahbaz

risposta

2

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).

+0

Che cos'è una radice in un albero non orientato? Inoltre, come faccio a sapere quanto sono grandi i sottoalberi? – Listing

+0

Come ho già detto, se non si dispone di una radice, è possibile selezionare qualsiasi nodo come root. E per sapere quanto sono grandi i sottoalberi, devi calcolarlo, idealmente mettendo in cache il risultato, in modo da non doverlo contare più volte. – svick

+0

Questo è sicuramente più di O (n), immagina di iniziare dal nodo A nell'esempio. Per prima cosa devi eseguire la scansione dell'intero sottoalbero, quindi passare a B, quindi a C e così via e ogni volta che esegui la scansione dell'intero sottoalbero che dà tempi più alti. – Listing

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.

0

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.