DAA - Pattern di unione ottimale

Unisci un insieme di file ordinati di diversa lunghezza in un unico file ordinato. Dobbiamo trovare una soluzione ottimale, in cui il file risultante verrà generato in un tempo minimo.

Se viene fornito il numero di file ordinati, esistono molti modi per unirli in un unico file ordinato. Questa unione può essere eseguita in coppia. Quindi, questo tipo di fusione è chiamato come2-way merge patterns.

Poiché accoppiamenti diversi richiedono quantità di tempo diverse, in questa strategia vogliamo determinare un modo ottimale per unire più file insieme. Ad ogni passaggio, vengono unite due sequenze più brevi.

Per unire un file p-record file e a q-record file richiede possibilmente p + q record di movimenti, la scelta più ovvia è, unire i due file più piccoli insieme ad ogni passaggio.

I modelli di unione a due vie possono essere rappresentati da alberi di unione binari. Consideriamo un insieme din file ordinati {f₁, f₂, f₃, …, f_n}. Inizialmente, ogni elemento di questo è considerato come un albero binario a nodo singolo. Per trovare questa soluzione ottimale, viene utilizzato il seguente algoritmo.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

Alla fine di questo algoritmo, il peso del nodo radice rappresenta il costo ottimale.

Esempio

Consideriamo i file dati, f ₁ , f ₂ , f ₃ , f ₄ e f _{5 rispettivamente} con 20, 30, 10, 5 e 30 numero di elementi.

Se le operazioni di unione vengono eseguite secondo la sequenza fornita, allora

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Quindi, il numero totale di operazioni è

50 + 60 + 65 + 95 = 270

Ora, sorge la domanda: esiste una soluzione migliore?

Ordinando i numeri in base alla loro dimensione in ordine crescente, otteniamo la seguente sequenza:

f₄, f₃, f₁, f₂, f₅

Quindi, le operazioni di unione possono essere eseguite su questa sequenza

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Pertanto, il numero totale di operazioni è

15 + 35 + 65 + 95 = 210

Ovviamente questo è migliore del precedente.

In questo contesto, risolveremo ora il problema utilizzando questo algoritmo.

Set iniziale

Passo 1

Passo 2

Passaggio 3

Passaggio 4

Quindi, la soluzione richiede 15 + 35 + 60 + 95 = 205 numero di confronti.