Algoritmos voraces#
Introducción#
Algoritmos voraces (greedy, glotones, ambiciosos)#
Consisten en intentar realizar en cada momento la mejor decisión para optimizar una función. En cada problema puede que no haya una única forma de hacer «lo mejor» en cada momento, así que a veces tenemos que elegir de entre varias formas de hacer las cosas cuál nos conviene.
Problema 11. Se tienen números enteros positivos distintos
50, 76, 72, 52, 70, 74, 84, 16, 43, 29, 31, 77, 22, 92, 46, 38, 91, 42, 48, 98, 87, 83, 6, 44, 7, 36, 80, 11, 10, 82, 67, 90, 18, 27, 37, 86, 33, 64, 26, 9
Problema 12. Se tienen
34, -51, -67, -42, -72, 27, -12, 55, -69, 47, 89, -54, 92, 8, 77, 82, -52, -48, -61, -90, 95, -49, 32, 18, 40, 96, 65, 44, 81, 24, 38, -4, -14, -97, -20, 63, 86, -98, -19, -8
Problema 13. Se tienen
355, 572, 532, 788, 82, 433, 225, 183, 499, 374, 734, 157, 121, 53, 486, 954, 792, 97, 684, 933, 51, 868, 485, 907, 292, 349, 804, 83, 214, 704, 200, 236, 404, 276, 778, 958, 105, 500, 334, 448, 836, 890, 537, 167, 31, 398, 313, 175, 930, 342
Problema 14. Se tiene la siguiente pirámide de números. Se comienza desde arriba y en cada paso se puede ir al número inferior, o bien al número inferior a la derecha, hasta que se llega a la fila de hasta abajo.
[7116]
[2675 8480]
[4356 6635 9218]
[7772 5841 2088 5391]
[4167 7727 3335 8931 4326]
[3838 2437 3248 9461 7437 6341]
[2117 5132 4482 1541 5000 8745 3782]
[6343 8811 6752 7523 2144 7855 9078 6472]
[1717 1943 8715 4741 3475 9590 7878 6717 4730]
[1683 1507 6681 1496 9129 7566 8605 3997 8064 7240]
[4668 9965 6544 1470 6365 8740 8637 6981 5703 9535 1509]
[7196 9964 7924 6509 8146 6239 4603 9728 1090 2069 8021 3227]
Por ejemplo, un posible camino es:
7116,2675,6635,2088,8931,9461,1541,2144,3475,9129,8740,4603
Hay que encontrar el camino que vaya de hasta arriba hasta abajo cuya suma de valores sea máxima.
Comenzamos con el siguiente problema.
Problema 11. Se tienen números enteros positivos distintos
50, 76, 72, 52, 70, 74, 84, 16, 43, 29, 31, 77, 22, 92, 46, 38, 91, 42, 48, 98, 87, 83, 6, 44, 7, 36, 80, 11, 10, 82, 67, 90, 18, 27, 37, 86, 33, 64, 26, 9
En este problema, el espacio de estados son todas posibles permutaciones de
Para resolver el problema, vamos a realizar un algoritmo voraz eligiendo los
Con esta idea, se puede proponer el siguiente algoritmo:
Poner los
en una lista de Python - TiempoTomar el
más grande y declarlo como - Tiempo .Eliminar ese
de la lista. - TiempoRepetir para ir definiendo
. En total, tiempo .
Este algoritmo toma
A=[50, 76, 72, 52, 70, 74, 84, 16, 43, 29, 31, 77, 22, 92, 46, 38, 91, 42, 48, 98, 87, 83, 6, 44, 7, 36, 80, 11, 10, 82, 67, 90, 18, 27, 37, 86, 33, 64, 26, 9]
A.sort()
print(A)
print(sum(i*a for i,a in enumerate(A)))
[6, 7, 9, 10, 11, 16, 18, 22, 26, 27, 29, 31, 33, 36, 37, 38, 42, 43, 44, 46, 48, 50, 52, 64, 67, 70, 72, 74, 76, 77, 80, 82, 83, 84, 86, 87, 90, 91, 92, 98]
53023
Vamos a mostrar que la permutación de
Pensemos que tenemos una permutación
Al pasar
por lo cual dicha permutación que habíamos tomado no puede ser la mayor.
Problema 12. Se tienen
34, -51, -67, -42, -72, 27, -12, 55, -69, 47, 89, -54, 92, 8, 77, 82, -52, -48, -61, -90, 95, -49, 32, 18, 40, 96, 65, 44, 81, 24, 38, -4, -14, -97, -20, 63, 86, -98, -19, -8
Una forma de resolver el problema es con exploración exhaustiva sobre el espacio de estados de subconjuntos de
Una mucho mejor forma de resolverlo es tomando de entre la lista los
A=[34, -51, -67, -42, -72, 27, -12, 55, -69, 47, 89, -54, 92, 8, 77, 82, -52, -48, -61, -90, 95, -49, 32, 18, 40, 96, 65, 44, 81, 24, 38, -4, -14, -97, -20, 63, 86, -98, -19, -8]
A.sort()
print(A)
print(len(A))
print(sum(j for j in A[:20]))
[-98, -97, -90, -72, -69, -67, -61, -54, -52, -51, -49, -48, -42, -20, -19, -14, -12, -8, -4, 8, 18, 24, 27, 32, 34, 38, 40, 44, 47, 55, 63, 65, 77, 81, 82, 86, 89, 92, 95, 96]
40
-919
Problema 13. Se tienen
355, 572, 532, 788, 82, 433, 225, 183, 499, 374, 734, 157, 121, 53, 486, 954, 792, 97, 684, 933, 51, 868, 485, 907, 292, 349, 804, 83, 214, 704, 200, 236, 404, 276, 778, 958, 105, 500, 334, 448, 836, 890, 537, 167, 31, 398, 313, 175, 930, 342
Una exploración exhaustiva permutando los bloques a acomodándolos seguro que resuelve el problema, pero el tiempo de ejecución será muy elevado.
Para resolver este problema, es mejor hacer lo siguiente:
Ordenamos los bloques de menor a mayor.
Ponemos el mayor hasta arriba, los siguientes dos en el nivel inferior, los siguientes tres en el inferior y así sucesivamente.
La altura máxima que podamos completar totalmente es la que se obtiene con este procedimiento.
lista=[355, 572, 532, 788, 82, 433, 225, 183, 499, 374, 734, 157, 121, 53, 486, 954, 792, 97, 684, 933, 51, 868, 485, 907, 292, 349, 804, 83, 214, 704, 200, 236, 404, 276, 778, 958, 105, 500, 334, 448, 836, 890, 537, 167, 31, 398, 313, 175, 930, 342]
lista.sort()
j=1
suma=0
piramide=[]
suma=1
while suma<len(lista):
fila=lista[suma-j:suma]
piramide.append(fila)
j+=1
suma+=j
print("La altura máxima es {} y se puede alcanzar con la siguiente pirámide:".format(len(piramide)))
for fila in piramide:
print(fila, "Esta fila tiene suma {}".format(sum(fila)))
La altura máxima es 9 y se puede alcanzar con la siguiente pirámide:
[31] Esta fila tiene suma 31
[51, 53] Esta fila tiene suma 104
[82, 83, 97] Esta fila tiene suma 262
[105, 121, 157, 167] Esta fila tiene suma 550
[175, 183, 200, 214, 225] Esta fila tiene suma 997
[236, 276, 292, 313, 334, 342] Esta fila tiene suma 1793
[349, 355, 374, 398, 404, 433, 448] Esta fila tiene suma 2761
[485, 486, 499, 500, 532, 537, 572, 684] Esta fila tiene suma 4295
[704, 734, 778, 788, 792, 804, 836, 868, 890] Esta fila tiene suma 7194
El análisis de tiempo y la correctitud quedan como tarea moral.
Problema 14. Se tiene la siguiente pirámide de números. Se comienza desde arriba y en cada paso se puede ir al número inferior, o bien al número inferior a la derecha, hasta que se llega a la fila de hasta abajo.
[7116]
[2675 8480]
[4356 6635 9218]
[7772 5841 2088 5391]
[4167 7727 3335 8931 4326]
[3838 2437 3248 9461 7437 6341]
[2117 5132 4482 1541 5000 8745 3782]
[6343 8811 6752 7523 2144 7855 9078 6472]
[1717 1943 8715 4741 3475 9590 7878 6717 4730]
[1683 1507 6681 1496 9129 7566 8605 3997 8064 7240]
[4668 9965 6544 1470 6365 8740 8637 6981 5703 9535 1509]
[7196 9964 7924 6509 8146 6239 4603 9728 1090 2069 8021 3227]
Por ejemplo, un posible camino es:
7116,2675,6635,2088,8931,9461,1541,2144,3475,9129,8740,4603
Hay que encontrar el camino que vaya de hasta arriba hasta abajo cuya suma de valores sea máxima.
Al ir de arriba hacia abajo tenemos dos opciones en cada paso, así que tenemos
Una forma de mejorar este procedimiento es usando un algoritmo voraz. Pero hay que ser muy cuidadosos. Si hacemos un algoritmo voraz que de arriba hacia abajo siempre seleccione la mejor opción, es posible que falle, pues puede que por tomar la dirección del número más grande en un paso local, acabemos descartando la posibilidad de tener un número muy grande más adelante. Por ejemplo, siguiendo esta heurística, en la siguiente pirámide iríamos en el primer paso a la derecha, hacia el
[10]
[36 54]
[99 20 24]
Sin embargo, eso no quiere decir que ningún algoritmo voraz funcione. A veces simplemente no hemos elegido el correcto. En este problema conviene mucho más realizar un algoritmo voraz de abajo hacia arriba. Para cada una de las entradas de la penúltima fila, ¿qué es lo mejor que puedo hacer después? Por ejemplo, en la pirámide chiquita de ejemplo, si ya llegamos al
[10]
[135 78]
A partir de aquí es claro lo que hay que hacer: del
En el penúltimo renglón escribimos lo mejor que podemos hacer.
De ahí, podemos decir qué es lo mejor que podemos hacer en el antepenúltimo.
Seguimos así sucesivamente hasta el primero.
Para recuperar el mejor camino, simplemente en cada paso hacemos lo mejor, pero considerado de esta forma.
Veamos la implementación
# Esta es una función auxiliar para leer la
# cadena de caracteres que tenemos y pasarla a una
# lista de listas de Python con la que podamos trabajar
# mejor.
entrada='''[7116]
[2675 8480]
[4356 6635 9218]
[7772 5841 2088 5391]
[4167 7727 3335 8931 4326]
[3838 2437 3248 9461 7437 6341]
[2117 5132 4482 1541 5000 8745 3782]
[6343 8811 6752 7523 2144 7855 9078 6472]
[1717 1943 8715 4741 3475 9590 7878 6717 4730]
[1683 1507 6681 1496 9129 7566 8605 3997 8064 7240]
[4668 9965 6544 1470 6365 8740 8637 6981 5703 9535 1509]
[7196 9964 7924 6509 8146 6239 4603 9728 1090 2069 8021 3227]'''
lineas=entrada.split('\n')
lista_buena=[]
for j in lineas:
lista_buena.append([int(k) for k in j[1:-1].split(' ')])
for linea in lista_buena:
print(linea)
[7116]
[2675, 8480]
[4356, 6635, 9218]
[7772, 5841, 2088, 5391]
[4167, 7727, 3335, 8931, 4326]
[3838, 2437, 3248, 9461, 7437, 6341]
[2117, 5132, 4482, 1541, 5000, 8745, 3782]
[6343, 8811, 6752, 7523, 2144, 7855, 9078, 6472]
[1717, 1943, 8715, 4741, 3475, 9590, 7878, 6717, 4730]
[1683, 1507, 6681, 1496, 9129, 7566, 8605, 3997, 8064, 7240]
[4668, 9965, 6544, 1470, 6365, 8740, 8637, 6981, 5703, 9535, 1509]
[7196, 9964, 7924, 6509, 8146, 6239, 4603, 9728, 1090, 2069, 8021, 3227]
# Ahora, lo que haremos es comenzar desde la linea 11 (índice 10) e iremos cambiando las entradas,
# de acuerdo a lo mejor que podemos hacer después. Ya hechos esos cambios, vamos a la línea 10,
# luego a la 9, y así sucesivamente.
for k in range(10,-1,-1):
for j in range(k+1):
lista_buena[k][j]=lista_buena[k][j]+max(lista_buena[k+1][j],lista_buena[k+1][j+1])
for linea in lista_buena:
print(linea)
[99733]
[80926, 92617]
[72408, 78251, 84137]
[61743, 68052, 71616, 74919]
[51812, 53971, 62211, 69528, 64923]
[47645, 46244, 44659, 58876, 60597, 59501]
[40792, 43807, 41411, 40245, 49415, 53160, 47708]
[29722, 38675, 36616, 36929, 38704, 44415, 43926, 38809]
[23329, 23379, 29864, 28849, 29406, 36560, 34848, 32337, 30350]
[21612, 21436, 21149, 16007, 24108, 25931, 26970, 20706, 25620, 24796]
[14632, 19929, 14468, 9616, 14511, 14979, 18365, 16709, 7772, 17556, 9530]
[7196, 9964, 7924, 6509, 8146, 6239, 4603, 9728, 1090, 2069, 8021, 3227]
Con esto tenemos que el mejor camino tiene suma
Sección 1#
Sección 2#
Sección 3#
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Problema
Problema
Problema
Problema
Problema