DAA - Modèle de fusion optimal

Fusionner un ensemble de fichiers triés de longueur différente en un seul fichier trié. Nous devons trouver une solution optimale, où le fichier résultant sera généré en un minimum de temps.

Si le nombre de fichiers triés est indiqué, il existe de nombreuses façons de les fusionner en un seul fichier trié. Cette fusion peut être effectuée par paire. Par conséquent, ce type de fusion est appelé2-way merge patterns.

Étant donné que différents appariements nécessitent des durées différentes, dans cette stratégie, nous voulons déterminer un moyen optimal de fusionner plusieurs fichiers ensemble. A chaque étape, les deux séquences les plus courtes sont fusionnées.

Pour fusionner un p-record file et un q-record file nécessite éventuellement p + q les mouvements d'enregistrement, le choix évident étant de fusionner les deux plus petits fichiers ensemble à chaque étape.

Les modèles de fusion bidirectionnelle peuvent être représentés par des arbres de fusion binaires. Considérons un ensemble den fichiers triés {f1, f2, f3, …, fn}. Au départ, chaque élément de ceci est considéré comme un arbre binaire à nœud unique. Pour trouver cette solution optimale, l'algorithme suivant est utilisé.

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

A la fin de cet algorithme, le poids du nœud racine représente le coût optimal.

Exemple

Considérons les fichiers donnés, f 1 , f 2 , f 3 , f 4 et f 5 avec respectivement 20, 30, 10, 5 et 30 éléments.

Si les opérations de fusion sont effectuées selon la séquence fournie, alors

M1 = merge f1 and f2 => 20 + 30 = 50

M2 = merge M1 and f3 => 50 + 10 = 60

M3 = merge M2 and f4 => 60 + 5 = 65

M4 = merge M3 and f5 => 65 + 30 = 95

Par conséquent, le nombre total d'opérations est

50 + 60 + 65 + 95 = 270

Maintenant, la question se pose: y a-t-il une meilleure solution?

En triant les nombres en fonction de leur taille dans un ordre croissant, nous obtenons la séquence suivante -

f4, f3, f1, f2, f5

Par conséquent, les opérations de fusion peuvent être effectuées sur cette séquence

M1 = merge f4 and f3 => 5 + 10 = 15

M2 = merge M1 and f1 => 15 + 20 = 35

M3 = merge M2 and f2 => 35 + 30 = 65

M4 = merge M3 and f5 => 65 + 30 = 95

Par conséquent, le nombre total d'opérations est

15 + 35 + 65 + 95 = 210

Évidemment, c'est mieux que le précédent.

Dans ce contexte, nous allons maintenant résoudre le problème à l'aide de cet algorithme.

Ensemble initial

Étape 1

Étape 2

Étape 3

Étape 4

Par conséquent, la solution prend 15 + 35 + 60 + 95 = 205 nombre de comparaisons.