algorithm
Algoritmos codiciosos

Observaciones

Problema continuo de la mochila.

Dados los artículos como (value, weight) debemos colocarlos en una mochila (contenedor) de una capacidad k . ¡Nota! ¡Podemos romper artículos para maximizar el valor!

Ejemplo de entrada:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

Rendimiento esperado:

maximumValueOfItemsInK = 20;

Algoritmo:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

Codificacion Huffman

El código de Huffman es un tipo particular de código de prefijo óptimo que se usa comúnmente para la compresión de datos sin pérdida. Comprime los datos de manera muy efectiva, ahorrando de 20% a 90% de memoria, dependiendo de las características de los datos comprimidos. Consideramos que los datos son una secuencia de caracteres. El codicioso algoritmo de Huffman utiliza una tabla que proporciona la frecuencia con la que aparece cada carácter (es decir, su frecuencia) para crear una forma óptima de representar cada carácter como una cadena binaria. El código de Huffman fue propuesto por David A. Huffman en 1951.

Supongamos que tenemos un archivo de datos de 100.000 caracteres que deseamos almacenar de forma compacta. Suponemos que solo hay 6 caracteres diferentes en ese archivo. La frecuencia de los personajes viene dada por:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

Tenemos muchas opciones sobre cómo representar tal archivo de información. Aquí, consideramos el problema de diseñar un código de carácter binario en el que cada carácter está representado por una cadena binaria única, que llamamos una palabra de código .

El árbol construido nos proporcionará:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

Si usamos un código de longitud fija , necesitamos tres bits para representar 6 caracteres. Este método requiere 300,000 bits para codificar el archivo completo. Ahora la pregunta es, ¿podemos hacerlo mejor?

Un código de longitud variable puede ser considerablemente mejor que un código de longitud fija, al dar caracteres frecuentes palabras en clave cortas y caracteres poco frecuentes palabras en código largas. Este código requiere: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bits para representar el archivo, lo que ahorra aproximadamente el 25% de la memoria.

Una cosa para recordar, consideramos aquí solo los códigos en los que ninguna palabra de código es también un prefijo de alguna otra palabra de código. Estos son llamados códigos de prefijo. Para la codificación de longitud variable, codificamos el archivo abc de 3 caracteres como 0.101.100 = 0101100, donde "." Denota la concatenación.

Los códigos de prefijo son deseables porque simplifican la decodificación. Dado que ninguna palabra de código es un prefijo de otro, la palabra de código que comienza un archivo codificado es inequívoca. Podemos simplemente identificar la palabra de código inicial, traducirla de nuevo al carácter original y repetir el proceso de decodificación en el resto del archivo codificado. Por ejemplo, 001011101 analiza únicamente como 0.0.101.1101, que se decodifica a aabe . En resumen, todas las combinaciones de representaciones binarias son únicas. Digamos, por ejemplo, si una letra se denota por 110, ninguna otra se denotará por 1101 o 1100. Esto se debe a que podría tener confusión sobre si seleccionar 110 o continuar concatenando el siguiente bit y seleccionando ese.

Técnica de compresión:

La técnica funciona creando un árbol binario de nodos. Estos pueden almacenarse en una matriz regular, cuyo tamaño depende del número de símbolos, n . Un nodo puede ser un nodo de hoja o un nodo interno . Inicialmente, todos los nodos son nodos de hoja, que contienen el símbolo mismo, su frecuencia y, opcionalmente, un enlace a sus nodos secundarios. Como convención, el bit '0' representa el hijo izquierdo y el bit '1' representa el niño derecho. La cola de prioridad se utiliza para almacenar los nodos, lo que proporciona al nodo la frecuencia más baja cuando se abre. El proceso se describe a continuación:

1. Cree un nodo de hoja para cada símbolo y agréguelo a la cola de prioridad.
2. Si bien hay más de un nodo en la cola:
   1. Eliminar los dos nodos de mayor prioridad de la cola.
   2. Cree un nuevo nodo interno con estos dos nodos como hijos y con una frecuencia igual a la suma de la frecuencia de los dos nodos.
   3. Agregue el nuevo nodo a la cola.
3. El nodo restante es el nodo raíz y el árbol de Huffman está completo.

Para nuestro ejemplo:

El pseudocódigo parece:

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

A pesar de que el tiempo lineal recibe una entrada ordenada, en general en los casos de una entrada arbitraria, el uso de este algoritmo requiere una clasificación previa. Por lo tanto, dado que la clasificación lleva tiempo O (nlogn) en casos generales, ambos métodos tienen la misma complejidad.

Como n aquí es el número de símbolos en el alfabeto, que suele ser un número muy pequeño (en comparación con la longitud del mensaje a codificar), la complejidad del tiempo no es muy importante en la elección de este algoritmo.

Técnica de descompresión:

El proceso de descompresión es simplemente una cuestión de traducir la secuencia de códigos de prefijo a un valor de byte individual, generalmente atravesando el nodo del árbol de Huffman por nodo a medida que se lee cada bit de la secuencia de entrada. Alcanzar un nodo hoja termina necesariamente la búsqueda de ese valor de byte en particular. El valor de la hoja representa el carácter deseado. Por lo general, el árbol Huffman se construye utilizando datos ajustados estadísticamente en cada ciclo de compresión, por lo que la reconstrucción es bastante simple. De lo contrario, la información para reconstruir el árbol debe enviarse por separado. El pseudocódigo:

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

Explicación codiciosa:
La codificación de Huffman examina la aparición de cada carácter y lo almacena como una cadena binaria de una manera óptima. La idea es asignar códigos de longitud variable a los caracteres de entrada, la longitud de los códigos asignados se basa en las frecuencias de los caracteres correspondientes. Creamos un árbol binario y lo operamos de manera ascendente para que los menos dos caracteres frecuentes estén lo más lejos posible de la raíz. De esta manera, el carácter más frecuente obtiene el código más pequeño y el carácter menos frecuente obtiene el código más grande.

Referencias:

• Introducción a los algoritmos: Charles E. Leiserson, Clifford Stein, Ronald Rivest y Thomas H. Cormen
• Codificación Huffman - Wikipedia
• Matemáticas discretas y sus aplicaciones - Kenneth H. Rosen

Problema de cambio

Dado un sistema monetario, ¿es posible dar una cantidad de monedas y cómo encontrar un conjunto mínimo de monedas correspondiente a esta cantidad?

Sistemas monetarios canónicos. Para algunos sistemas monetarios, como los que usamos en la vida real, la solución "intuitiva" funciona perfectamente. Por ejemplo, si las diferentes monedas y billetes en euros (excluyendo centavos) son 1 €, 2 €, 5 €, 10 €, lo que otorga la moneda o la factura más alta hasta que alcancemos la cantidad y la repetición de este procedimiento dará lugar al conjunto mínimo de monedas. .

Podemos hacer eso recursivamente con OCaml:

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

Estos sistemas están hechos para que el cambio sea fácil. El problema se vuelve más difícil cuando se trata de un sistema monetario arbitrario.

Caso general. ¿Cómo dar 99 € con monedas de 10 €, 7 € y 5 €? Aquí, dar monedas de 10 € hasta que nos queden con 9 € conduce obviamente a ninguna solución. Peor que una solución puede no existir. Este problema es de hecho np-hard, pero existen soluciones aceptables que mezclan la codicia y la memoria . La idea es explorar todas las posibilidades y elegir la que tenga el número mínimo de monedas.

Para dar una cantidad X> 0, elegimos una pieza P en el sistema monetario y luego resolvemos el subproblema correspondiente a XP. Intentamos esto para todas las piezas del sistema. La solución, si existe, es la ruta más pequeña que llevó a 0.

Aquí una función recursiva OCaml correspondiente a este método. Devuelve Ninguno, si no existe solución.

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

Nota : Podemos observar que este procedimiento puede calcular varias veces el cambio establecido para el mismo valor. En la práctica, el uso de la memoria para evitar estas repeticiones conduce a resultados más rápidos (mucho más rápidos).

Problema de selección de actividad

El problema

Tienes un conjunto de cosas que hacer (actividades). Cada actividad tiene una hora de inicio y una hora de finalización. No se le permite realizar más de una actividad a la vez. Su tarea es encontrar una manera de realizar el número máximo de actividades.

Por ejemplo, suponga que tiene una selección de clases para elegir.

Recuerda, no puedes tomar dos clases al mismo tiempo. Eso significa que no puede tomar clases 1 y 2 porque comparten un horario común de 10.30 a 11.00 AM. Sin embargo, puede tomar clases 1 y 3 porque no comparten una hora común. Por lo tanto, su tarea es tomar el máximo número de clases posible sin ninguna superposición. Como puedes hacer eso?

Análisis

Pensemos en la solución mediante un enfoque codicioso. En primer lugar, elegimos aleatoriamente algún enfoque y comprobamos que funcionará o no.

• ordene la actividad por hora de inicio, lo que significa que la actividad comienza primero, la tomaremos primero. luego tome primero al último de la lista ordenada y verifique que se intersecará con la actividad tomada anteriormente o no. Si la actividad actual no se interseca con la actividad tomada anteriormente, realizaremos la actividad de lo contrario no realizaremos. Este enfoque funcionará para algunos casos como

el orden de clasificación será 4 -> 1 -> 2 -> 3. La actividad 4 -> 1 -> 3 se realizará y la actividad 2 se omitirá. Se realizará la actividad máxima de 3. Funciona para este tipo de casos. pero fallará para algunos casos. Vamos a aplicar este enfoque para el caso.

El orden de clasificación será 4 -> 1 -> 2 -> 3 y solo se realizará la actividad 4, pero la respuesta puede ser la actividad 1 -> 3 o 2 -> 3. Así que nuestro enfoque no funcionará para el caso anterior. Probemos otro enfoque

• Ordene la actividad por duración de tiempo, lo que significa realizar primero la actividad más corta. Eso puede solucionar el problema anterior. Aunque el problema no está completamente resuelto. Todavía hay algunos casos que pueden fallar la solución. Aplicar este enfoque en el caso abajo.

Si ordenamos la actividad por tiempo, el orden será 2 -> 3 ---> 1. y si realizamos la actividad No. 2 primero, entonces no se puede realizar ninguna otra actividad. Pero la respuesta será realizar la actividad 1 y luego realizar 3. Por lo tanto, podemos realizar una actividad máxima de 2. Entonces, esto no puede ser una solución para este problema. Debemos intentar un enfoque diferente.

La solución

• Ordene la Actividad por hora de finalización, lo que significa que la actividad termina primero que viene primero. el algoritmo se da a continuación

1. Ordenar las actividades por sus tiempos finales.
2. Si la actividad a realizar no comparte un tiempo común con las actividades que se realizaron anteriormente, realice la actividad.

Analicemos el primer ejemplo.

ordene la actividad por sus tiempos finales, así que el orden será 1 -> 5 -> 2 -> 4 -> 3 .. la respuesta es 1 -> 3 estas dos actividades se llevarán a cabo. y esa es la respuesta. Aquí está el código sudo.

1. ordenar: actividades
2. realizar la primera actividad de la lista ordenada de actividades.
3. Conjunto: Actividad_actual: = primera actividad
4. set: end_time: = end_time de la actividad actual
5. Vaya a la siguiente actividad si existe, si no existe, finalice.
6. if start_time of current activity <= end_time: realice la actividad y vaya a 4
7. otra cosa: llegó a 5.

Consulte aquí para obtener ayuda sobre la codificación http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/