Este tipo de algoritmo
recibe muchos nombres distintos: voraz, goloso, devorador, codicioso, greedy,…Se
basa en la estrategia de elegir en cada paso la solución óptima del problema,
esperando que, al reiterar esta estrategia, se construya una solución óptima
global. Para conseguirlo, no da marcha atrás en las decisiones si no se llega a
un óptimo. Esto lo hace más rápido, pero más inseguro, porque no hay garantía
de consecución de objetivos.
Ha de ser posible la elección
óptima en cada paso, como en el caso de descomposición en suma de factoriales,
que siempre se puede conocer el mayor factorial menor o igual que el número
dado
Aquí estudiaremos varios
ejemplos de descomposición de un número entero positivo en sumandos de un
cierto tipo. Un ejemplo claro es el de encontrar una suma de factoriales cuyo
resultado sea un número dado. Este algoritmo lo llevamos usando años en
nuestras publicaciones, porque es rápido, aunque en ocasiones produce
soluciones con un número alto de sumandos.
Lo vemos con un ejemplo
elegido al azar, el número 1329, al que queremos convertir en una suma de
factoriales lo menos extensa posible.
Es claro que si no deseamos
muchos sumandos, vayamos eligiendo los factoriales mayores posibles para construir
la suma. Podríamos efectuarlo así:
1329-720=609
609-120=489
489-120=369
369-120=249
249-120=129
129-120=9
9-6=3
3-2=1
1-1=0
Con ello, hemos descompuesto
1329 en suma de factoriales:
1329=720+120+120+120+120+120+6+2+1
Basta analizar la solución
para darnos cuenta de que no podemos esperar demasiado de este algoritmo, pero
al contar con el 1 entre los factoriales, siempre dará solución.
Un caso similar es el de
descomponer una fracción en fracciones egipcias (del tipo 1/p). Bastará ir
buscando en el numerador el mayor divisor posible del denominador (suponemos
fracción irreducible). Por ejemplo, la fracción 17/24 se puede descomponer de
esta forma, eligiendo en el numerador sucesivamente los mayores divisores de
24:
17/24=(12+4+1)/24=1/2+1/6+1/24
Los dos ejemplos los hemos
desarrollado de forma manual, pero es claro que se podrá automatizar
fácilmente.
Para planificar los
algoritmos, distinguiremos dos variantes:
La primera requerirá que los
sumandos pertenezcan a un mismo tipo, como los factoriales de más arriba, o,
por ejemplo el problema de descomponer un número en sumandos triangulares.
La segunda, muy parecida a
la primera, deberá elegir los sumandos dentro de una lista, como en el problema
de las monedas, en el que una cantidad hay que traducirla a un conjunto de
monedas con distintos valores.
En realidad, el ejemplo de
los factoriales se puede considerar de este segundo tipo, por su escasez.
Sumandos
del mismo tipo
Si el sumando óptimo lo
debemos elegir dentro de un tipo, como primos, cuadrados o pentagonales,
podremos usar un sencillo algoritmo que el autor usa con frecuencia. Tendría
esta estructura, en la que, para un número n
y un tipo dado, devuelve la suma más adecuada que un algoritmo codicioso puede
dar.
Function codicioso$(n)
Dim c$
Dim i, r, s,suma
Dim vale As Boolean
suma = 0 'Irá
sumando progresivamente
i = n ‘Recorrerá
los posibles sumandos
r = n ‘Posible
sumando válido
c = "" ’Recogerá
soluciones
While i > 0 ‘Recorremos
de mayor a menor, para optimizar
vale = False ‘Aún
no hay solución
if CONDICION then vale=true ‘La
CONDICIÓN dependerá del tipo de sumandos
If vale Then
c$ = c$ + Str$(i) +
" "
suma=suma+i
‘Si existe solución,
se resta y se incorpora a la suma
r = r - i: i = r
Else
‘Si no existe
solución, se sigue buscando el óptimo, descendiendo
i = i – 1
end if
Wend
If suma=n then codicioso = c
else codicioso=”NO”
End Function
Por ejemplo, si la condición
es la de ser primo, usaríamos la función ESPRIMO, fácilmente localizable en
nuestro blog. En la tabla siguiente se recogen las sumas en números primos, si
es que son posibles, para los primeros números de tres cifras:
Este ejemplo es muy
interesante, porque ilustra las limitaciones de los algoritmos codiciosos. En
primer lugar, sólo figuran los números en los que, al finalizar el algoritmo,
la suma coincide con ellos, sin dejar ningún residuo no primo. Por ejemplo, el
15 daría como resultado 7+7, y sobraría 1, porque no es primo. En segundo lugar,
al no explorar todas las posibilidades, ignora las sumas de Golbach para
números pares, porque se detiene antes de llegar a los dos primos que predice
la conjetura. Por ejemplo, el número 104, que no figura en la tabla, presenta
varias descomposiciones en sumas de dos primos, y el algoritmo codicioso las
ignora:
No obstante, en sumados de
algunos tipos, el algoritmo funciona relativamente bien. Por ejemplo, cuando el
1 pertenece a ese tipo, como ocurriría en los cuadrados, triangulares,
palindrómicos o de Fibonacci, la descomposición siempre será exitosa, aunque,
quizás, algo larga. También suele funcionar bien con primos y cuadrados de
primos, y con oblongos si el número es par. El siguiente ejemplo contiene
resultados de cuadrados de primos entre 375 y 400:
En este caso están
condicionados por el cuadrado de 19, 361. En general suelen aparecer los
ejemplos con una cierta rapidez.
Un ejemplo clásico, y que
publicamos a veces, es el de la representación de Zeckendorf, en la que todo
número es suma de elementos de la sucesión de Fibonacci (ver, por ejemplo,
nuestra entrada
https://hojaynumeros.blogspot.com/2020/09/representacion-de-zeckendorf.html).
En ella el algoritmo indicado es el codicioso. Hemos aplicado la función que
presentamos más arriba a un conjunto de números consecutivos, y observamos que
todos están representados así:
Puedes decubrir aspectos muy interesantes sobre esta
descomposición en
https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
Sumandos
dentro de una lista
Este otro tipo de
descomposición en sumandos que se adapta bien a los algoritmos codiciosos, es
el de expresar un número como suma de números ya fijados en una lista. De este
tipo es el problema de las monedas, en el que hay que encontrar la forma de
pagar una cantidad si se dispone de un número suficiente de monedas de varias
clases.
En este blog hemos tratado
este tema y otros similares, como el de los números McNugget y la
representación de un número respecto a una lista:
https://hojaynumeros.blogspot.com/2010/02/frobenius-y-los-mcnuggets.html
https://hojaynumeros.blogspot.com/2012/11/descomposicion-de-un-numero-segun-una.html
Por ejemplo, si nos piden
representar el número 80 mediante los números de la lista 2, 4, 14, 32,
procederíamos como en los problemas anteriores, restando de 80 el número mayor
posible cada vez, y usando repeticiones:
48=80-32; 16=38-32; 16=14+2
Luego 80=32+32+14+2
No hemos necesitado el
sumando 4.
El procedimiento usado para
sumandos del mismo tipo es válido aquí, pero deberemos iniciar el algoritmo
declarando los elementos de la lista según un vector.
Algo similar usa las
herramientas que ofrecemos en hojamat.es:
http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum
http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#mcnugget
Aquí seguiremos usando una
función como en el primer caso, pero declarando los sumandos. Los
introduciremos como componentes de un vector. Por ejemplo, en el siguiente
listado se pretende encontrar qué monedas y billetes de euro podemos usar en
una compra ordinaria, sin céntimos, y con un tope del billete de 50€:
Function codicioso3$(n)
Dim c$
Dim i, j, r, s, suma, tope
Dim v(20) ‘Usamos
un vector de 20 componentes
v(1) = 1: v(2) = 2: v(3) =
5: v(4) = 10: v(5) = 20: v(6) = 50
tope = 6 ‘Determinamos
seis monedas y billetes
‘El resto del listado
es muy similar al del anterior tipo
suma = 0 'Irá
sumando progresivamente
i = n 'Recorrerá
los posibles sumandos
r = n 'Posible
sumando válido
c = "" 'Recogerá
soluciones
j = tope
While i > 0 And j > 0 'Recorremos
de mayor a menor, para optimizar
If i >= v(j) Then
c$ = c$ + Str$(v(j)) +
" "’Aquí
sumamos componentes del vector
suma = suma + v(j)
i = i - v(j)
Else
'Si no existe
solución, se sigue buscando el óptimo, descendiendo
j = j - 1
End If
Wend
If suma = n Then codicioso3
= c Else codicioso3 = "NO"
End Function
Como ejemplo, insertamos una
tabla con algunas cantidades en euros y su descomposición en monedas y
billetes:
Hay que volver a advertir
que estas soluciones no han de ser ni únicas ni óptimas.
