DAA - Patrón de fusión óptimo
Combine un conjunto de archivos ordenados de diferente longitud en un solo archivo ordenado. Necesitamos encontrar una solución óptima, donde el archivo resultante se generará en un tiempo mínimo.
Si se proporciona el número de archivos ordenados, hay muchas formas de combinarlos en un solo archivo ordenado. Esta combinación se puede realizar por parejas. Por lo tanto, este tipo de fusión se denomina2-way merge patterns.
Dado que los diferentes emparejamientos requieren diferentes cantidades de tiempo, en esta estrategia queremos determinar una forma óptima de fusionar muchos archivos. En cada paso, se fusionan dos secuencias más cortas.
Para fusionar un p-record file y un q-record file requiere posiblemente p + q movimientos de registro, siendo la elección obvia fusionar los dos archivos más pequeños en cada paso.
Los patrones de fusión bidireccionales se pueden representar mediante árboles de fusión binarios. Consideremos un conjunto den archivos ordenados {f1, f2, f3, …, fn}. Inicialmente, cada elemento de esto se considera como un árbol binario de un solo nodo. Para encontrar esta solución óptima, se utiliza el siguiente 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);Al final de este algoritmo, el peso del nodo raíz representa el costo óptimo.
Ejemplo
Consideremos los archivos dados, f 1 , f 2 , f 3 , f 4 y f 5 con 20, 30, 10, 5 y 30 números de elementos respectivamente.
Si las operaciones de combinación se realizan de acuerdo con la secuencia proporcionada, entonces
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
Por tanto, el número total de operaciones es
50 + 60 + 65 + 95 = 270
Ahora, surge la pregunta: ¿hay alguna solución mejor?
Clasificando los números según su tamaño en orden ascendente, obtenemos la siguiente secuencia:
f4, f3, f1, f2, f5
Por lo tanto, las operaciones de combinación se pueden realizar en esta secuencia
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
Por tanto, el número total de operaciones es
15 + 35 + 65 + 95 = 210
Evidentemente, este es mejor que el anterior.
En este contexto, ahora vamos a resolver el problema utilizando este algoritmo.
Conjunto inicial
Paso 1
Paso 2
Paso 3
Etapa 4
Por lo tanto, la solución requiere 15 + 35 + 60 + 95 = 205 número de comparaciones.