Concepto de algoritmo voraz (qué es, para qué sirve) estrategias de programación

[foxternoster]

Alguien puede explicar con palabras sencillas el concepto de algoritmo voraz?

[Alex Rodríguez]

Un algoritmo voraz viene siendo un algoritmo para un problema de optimización que va construyendo la solución escogiendo los mejores elementos de entre todos los posibles, sin tener que revisar las decisiones que se toman.

Un ejemplo: supongamos que estás haciendo una dieta y quieres ingerir el menor número de calorías posibles pero necesitas ingerir un volumen V de alimentos mínimo para sentir saciedad. Dispones de n alimentos cada uno de los cuales te aporta unas calorías c(i) y un volumen v(i) y estos alimentos se pueden partir (fraccionar) si no te los quieres comer enteros. Lo primero que tendrías que hacer es calcular cuántas calorías por unidad de volumen te proporciona cada alimento, porque te interesará irte comiendo los que tengan menos calorías por unidad de volumen. Una vez los tengas ordenados te los empiezas a comer hasta que llegues al alimento que ya no te cabe completo en la barriga. Ese lo partes para completar el volumen V y te lo comes, con lo cual habrás completado el objetivo de comerte el volumen V ingiriendo el menor número de calorías posibles.

La clave del asunto es que hay un criterio de selección (menor aporte de calorías por unidad de volumen) que te permite elegir sin equivocarte. Hay otros casos donde no puedes estar seguro de elegir sin equivocarte y entonces no te vale un algoritmo voraz.

[foxternoster]

Creo que mas o menos lo he entendido de todas formas si pudieras poner un ejemplo con números te lo agradecería 

[Alex Rodríguez]

Ok, lo preparo y lo pongo...

[Alex Rodríguez]

El planteamiento sería el siguiente: necesitas ingerir un volumen V de alimentos mínimo que es de 360 mililitros (ml) y quieres hacerlo consumiendo el menor número de calorías posibles. Para ello dispones de los siguientes alimentos:

Nº alimento|   Nombre Alimento   | Volumen alimento | Calorías alimento
1                 |   Pan redondo         | 150 ml                   | 150 cal
2                 |   Bistec magro         | 80 ml                     | 145 cal
3                 |   Bistec ternera       | 95 ml                     | 145 cal
4                 |   Lechuga cruda      | 205 ml                   | 85 cal
5                 |   Tomate asado      | 55 ml                     | 60 cal
6                 |   Tortilla francesa    | 190 ml                   | 210 cal
7                 |   Pescado crudo      | 70 ml                     | 105 cal
8                 |   Mango maduro      | 60 ml                     | 35 cal
9                 |   Morcilla serrana     | 200 ml                   | 435 cal
10               |   Pimiento verde     | 50 ml                       | 35 cal
11                |   Pimiento rojo       | 50 ml                       | 35 cal
12                |   Longaniza           | 20 ml                       | 135 cal
13                |   Shushi                 | 90 ml                       | 155 cal

Tienes que elegir qué alimentos comer, o mejor dicho, tienes que diseñar un algoritmo para que el ordenador te diga qué alimentos debes comer. El primer paso será ordenar los alimentos por orden de calorías aportadas por unidad de volumen.

[Alex Rodríguez]

El cálculo nos da el siguiente resultado:

Nº alimento|   Nombre Alimento   | Volumen alimento | Calorías alimento  | cal/ud vol
1                 |   Pan redondo         | 150 ml                   | 150 cal                  |    1
2                 |   Bistec magro         | 80 ml                     | 145 cal                  |    1,8125
3                 |   Bistec ternera       | 95 ml                     | 145 cal                   |   1,5263
4                 |   Lechuga cruda      | 205 ml                   | 85 cal                     |    0,4146
5                 |   Tomate asado      | 55 ml                     | 60 cal                     |     1,0909
6                 |   Tortilla francesa    | 190 ml                   | 210 cal                   |    1,1053
7                 |   Pescado crudo      | 70 ml                     | 105 cal                   |    1,5
8                 |   Mango maduro      | 60 ml                     | 35 cal                     |    0,5833
9                 |   Morcilla serrana     | 200 ml                   | 435 cal                   |    2,175
10                |   Pimiento verde     | 50 ml                       | 35 cal                    |     0,7
11                |   Pimiento rojo       | 50 ml                       | 35 cal                    |    0,7
12                |   Longaniza           | 20 ml                       | 135 cal                   |   6,75
13                |   Shushi                 | 90 ml                       | 155 cal                   |   1,722

Hemos hecho el cálculo pero todavía no hemos ordenado los alimentos por calorías aportadas por unidad de volumen, que es lo siguiente que hemos de hacer.

[Alex Rodríguez]

Ahora nos olvidamos de cómo estaban ordenados los alimentos inicialmente y los ordenamos en base a la cantidad de calorías que aportan por unidad de volumen (de menor a mayor), nos queda esto:

Nº orden|   Nombre Alimento   | Volumen alimento | Calorías alimento  | cal/ud vol
1                 |   Lechuga cruda      | 205 ml                   | 85 cal                     |    0,4146
2                 |   Mango maduro      | 60 ml                     | 35 cal                     |    0,5833
3                 |   Pimiento verde     | 50 ml                       | 35 cal                    |     0,7
4                |   Pimiento rojo       | 50 ml                       | 35 cal                     |    0,7
5                 |   Pan redondo         | 150 ml                   | 150 cal                  |    1
6                 |   Tomate asado      | 55 ml                     | 60 cal                     |     1,0909
7                 |   Tortilla francesa    | 190 ml                   | 210 cal                   |    1,1053
8                 |   Pescado crudo      | 70 ml                     | 105 cal                   |    1,5
9                 |   Bistec ternera       | 95 ml                     | 145 cal                   |   1,5263
10               |   Shushi                 | 90 ml                       | 155 cal                   |   1,722
11               |   Bistec magro         | 80 ml                     | 145 cal                   |    1,8125
12               |   Morcilla serrana     | 200 ml                   | 435 cal                   |    2,175
13               |   Longaniza           | 20 ml                       | 135 cal                   |   6,75

[Alex Rodríguez]

Ya tenemos preparado lo que nos vamos a comer; ahora se trata de irlo comiendo hasta llegar justo al alimento con el que completaremos nuestro volumen V de alimentos mínimo. Como nos interesa ingerir el volumen mínimo exactamente, ni más, ni menos, el último alimento posiblemente tengamos que partirlo, a no ser que dé la casualidad de que comiéndolo entero completemos justo nuestro volumen.

[Alex Rodríguez]

El volumen a ingerir es de 360 mililitros, comenzamos a comer. Antes de comer un alimento tenemos que comprobar que comiéndolo no sobrepasamos el volumen a ingerir.

¿Comiendo la lechuga cruda sobrepasamos el volumen? No, nos comemos la lechuga cruda, llevamos 205 ml de volumen y 85 calorías.

¿Comiendo el mango maduro sobrepasamos el volumen? No, nos comemos el mango maduro, llevamos 265 ml de volumen y 120 calorías.

¿Comiendo el pimiento verde sobrepasamos el volumen? No, nos comemos el pimiento verde, llevamos 315 ml de volumen y 155 calorías.

¿Comiendo el pimiento rojo sobrepasamos el volumen? Sí, llegaríamos a 365 mililitros y nosotros hemos dicho que solo queremos llegar a 360.

[Alex Rodríguez]

Entonces hemos de trocear el pimiento rojo en dos partes, una de 45 ml y otra de 5 ml. Nos comeremos solo la parte de 45 ml. Las calorías que nos aportan la podemos calcular con una regla de tres o como (45/50) * 35 = 0,9 * 35 = 31,5 calorías

El volumen total ingerido será de 360 ml que era nuestro objetivo, y las calorías totales ingeridas 186,5

[foxternoster]

Gracias Alex, la explicacion me ha parecido clara pero lo que no veo es codigo ni pseudocodigo, es decir, dónde está el algoritmo

[nikkoo]

gracias pro la explicacion

[Alex Rodríguez]

Como bien dices foxternoster, no tenemos el algoritmo. Pero la idea es que antes de plantear un algoritmo tenemos que tener claro el proceso que debe realizar dicho algoritmo. Si lo tenemos claro, ya podemos proceder a plantear el algoritmo 

[foxternoster]

¿Podrías poner el planteamiento?

[Alex Rodríguez]

El planteamiento podría ser algo así:

funcion ElegirDieta (Lista de alimentos datos, decimal Volumen): devuelve Lista de alimentos resultado

variables
    decimal VolumenAlimentosIngeridos
    decimal CantidadCaloriasIngeridas
finVariables

Para cada alimento en datos
     calcular calorías por ud de volumen de alimento
FinPara

OrdenarListaPorCriterio (datos, calorías por ud de volumen de alimento)

Para cada alimento en listaOrdenadaAlimentos
Si VolumenAlimentosIngeridos < Volumen
        Ingerir próximo alimento en datos
siNo
       CalcularFracciónAIngerir
       IngerirFracción
FinSi

FinPara

FinFuncion

[foxternoster]

Esto supongo que habría que pasarlo a un programa pero pasar esto a un programa no es fácil ¿no?

[Alex Rodríguez]

Efectivamente este planteamiento para hacerlo funcionar sobre un ordenador habría que pasarlo a un programa desarrollado en un lenguaje concreto como c, c++, java, visual basic o cualquier otro. Si es fácil o difícil pues depende de la destreza que tenga cada uno, no puede considerarse complicado pero tampoco es algo inmediato que se resuelva en cinco minutos.