Existe un buen número de métodos que los matemáticos y científicos emplean cuando deben resolver problemas complejos. Uno de los más versátiles y simples de entender es el denominado “algoritmo voraz” (Greedy algorithm). A pesar de que no siempre es capaz de encontrar una respuesta óptima, se lo utiliza con frecuencia dado que es muy rápido. Te contamos en qué consiste, qué ventajas tiene y cómo utilizarlo.
Para resolver un problema se deben seguir una serie de pasos. Estos pasos deben estar claramente definidos, sin importar que vayan a ser ejecutados por un ordenador o por un humano. La correcta definición de esos pasos garantiza que si se aplica el sistema dos veces a un determinado problema, la solución será la misma. Esta verdadera “receta” se llama algoritmo, y no es otra cosa que una secuencia de pasos ordenados y finitos con los que podemos resolver un problema determinado en un tiempo mínimo. El vocablo “algoritmo” proviene del latín “dixit algorithmus”, y éste a su vez del nombre de un matemático persa llamado Muhammad ibn Musa al-Jwarizmi.
El algoritmo voraz
Hay problemas que a pesar de tener un planteo sumamente sencillo, carecen de una solución que pueda ser considerada trivial. Imaginemos, por ejemplo, un viajante de comercio que debe recorrer 25 ciudades distribuidas por el interior de España: ¿de qué forma debería hacerlo para completar su trabajo recorriendo el menor número de kilómetros posible?
Esto se debe a que la cantidad de recorridos posibles es de 25! (25 factorial, o sea, 1 x 2 x 3 x 4 x 5 x ... x 24 x 25), es decir, hay 15.511.210.043.330.985.984.000.000 recorridos para probar y descartar antes de saber cuál es el óptimo. Analizando mil millones de recorridos por segundo, demoraríamos 491.857.244 años en averiguar cuál es el recorrido óptimo para nuestro viajante. Esto sirve para darnos cuenta de la importancia que tiene un algoritmo rápido, aun cuando no siempre sea capaz de encontrar el mejor resultado posible.
El denominado “algoritmo voraz” sigue una estrategia sencilla pero eficaz. Simplemente, se trata de elegir la opción óptima en cada paso local, con la esperanza de llegar a una solución general óptima. En el ejemplo de nuestro viajante de comercio, cada paso podría ser tan simple como -estando en la ciudad “A” - dirigirse a la más cercana que aún no hayamos visitado. Una vez allí, repetir el procedimiento una y otra vez hasta que hayamos completado el recorrido. Seguramente no obtendremos un resultado óptimo, pero puede encontrarse un camino bastante bueno en un tiempo despreciable.
Este tipo de algoritmo, a veces llamado ávido, devorador o goloso, es el que menos dificultades presenta a los investigadores que deben diseñar y comprobar el funcionamiento de diferentes estrategias. El nombre “voraz” se debe a que, en cada paso, el algoritmo escoge el mejor pedazo que es capaz de comer sin preocuparse de los pasos que restan hasta encontrar la solución. Un algoritmo de este tipo nunca deshace una decisión ya tomada: una vez incorporado, un “candidato a la solución” (ir de la ciudad “A” a la “B”, por ejemplo) formará parte de la solución. Y cada candidato rechazado es eliminado definitivamente.
Una vez aclarado el hecho de que los algoritmos voraces proceden por pasos, podemos ver en detalle cómo es su estructura. Se parte de un conjunto de candidatos que se encuentra vacío, es decir, no hay ninguna solución. Luego, en cada paso, se intenta añadir al conjunto el mejor candidato entre las soluciones que aún no han sido escogidas, a través de una función de selección. Luego de cada incorporación se comprueba si el conjunto de candidatos resultante es una solución del problema. Su esquema genérico es el siguiente:
función voraz(C:conjunto):conjunto { C es el conjunto de todos los candidatos } S <= vacio { S es el conjunto en el que se construye la solución} mientras ¬solución(S) y C <> vacío hacer x <= el elemento de C que maximiza seleccionar(x) C <= C {x} si completable(S U {x}) entonces S <= S U {x} si solución(S) entonces devolver S si no devolver no hay soluciónPara comprender exactamente su funcionamiento podemos aplicarlo a otro problema sencillo: Supongamos que disponemos de un grupo compuesto por cuatro tipos billetes de banco: diez billetes de 5, cinco de 10, tres de 20 y dos de 50. Tenemos que hacer un pago de 100 euros con el menor número de billetes posible ¿qué billetes debemos escoger? La solución obvia consiste en utilizar dos billetes de cincuenta euros, pero ¿cómo llegaría a esa solución un ordenador? Muy simple: utilizando el algoritmo voraz.
Al plantear ese problema, el “candidato” (c) sería un conjunto finito de billetes, la “solución” (S) el conjunto de billetes buscados y cuya suma es la cantidad a pagar, “completable” es la suma de billetes escogidos en un momento dado y que no supera la cantidad a pagar, y la “función de selección” no es otra cosa que la encargada de seleccionar el billete de mayor valor disponible en el conjunto de candidatos aún no seleccionados.
En el primer paso se elegiría uno de los billetes de mayor valor disponibles (uno de 50). Luego de comprobar que no se llegó a la solución se tomaría nuevamente uno de los billetes de mayor valor disponibles (el restante de 50) y se comprobaría que hemos llegado a la solución. Simple de implementar, ¿verdad?
Mmmm...me servira pa buscar mis calcetines en la mañana =)
No termino de entender esto de algoritmo voraz, me parece la manera mas logica de proceder por ejemplo con el de los viajes, elegis un punto y de ahi vas recorriendo por el mas cercano, o sea si ese es el planeamiento q gracia tendria ir de un punto al mas lejano, ni siquiera haces esa combinacion al empezar, asi q no seria nunca necesario el 25!
Interesante, lo raro es que nunca lo había escuchado. En algunas presenta la solución optima, en otras aunque no garantiza la mejor selección si presenta una de las mejores altenativas. Gracias Neoteo.
¿Este algoritmo no hace lo mismo que los autómatas celulares?
Hola gente, me encanta el articulo, me hizo acordar a cuando programaba en visual, ja, yo usaba cosas asi para soluciones, a ver, aca les dejo algo que hice recien, estoy en el laburo mucho mas no puedo pensar pero se que se puede hacer mas sintetico.
Bien, una persona nos pide que le paguemos 100 euros (o pesos aca en ARG.), y tenemos 2 posibilidades, una pagar justo con la menos cantidad de billetes como dijeron aca, y la otra que se me ocurrio agregar, pagarle dandole cambio, que a veces pasa..
Entonces lo que hacemos primero es ver los billetes que tenemos en la billetera, y suponiendo que ya los contamos quedamos que tenemos este dinero:
cinco = 10
diez = 5
veinte = 3
cincuenta = 2
O sea que tengo 10 billetes de 5 euros 5 de 10 euros etc...
Ahora algo asi seria mi programacion...
Conteo del dinero (Conteo)
Quiere cambio (camb = 1)
NO quiere cambio (camb = 0)
valor a pagar (V = 100)
if camb = 1 then
do
do
if conteo = v then exit do
conteo = conteo + 5
cinco = cinco - 1
loop until cinco = 0
do
if conteo = v then exit do
conteo = conteo + 10
diez = diez - 1
loop until diez = 0
do
if conteo = v then exit do
conteo = conteo + 20
veinte = veinte - 1
loop until veinte = 0
do
if conteo = v then exit do
conteo = conteo + 50
cincuenta = cincuenta - 1
loop until cincuenta = 0
loop until Conteo = v
Listo la persona se fue con el pago y le hicimos el favor de darle cambio.
else
do
do
if conteo = v then exit do
conteo = conteo + 50
cincuenta = cincuenta - 1
loop until cincuenta = 0
do
if conteo = v then exit do
conteo = conteo + 20
veinte = veinte - 1
loop until veinte = 0
do
if conteo = v then exit do
conteo = conteo + 10
diez = diez - 1
loop until diez = 0
do
if conteo = v then exit do
conteo = conteo + 5
cinco = cinco - 1
loop until cinco = 0
loop until Conteo = v
Listo la persona se va con el dinero justo
end if
Se entendio? no lo probe pero cuando llegue a casa lo pongo en visual a ver que onda ja...
Saludos a todos
Me gustaría saber a quien se le ocurrió ponerle ese nombre,
como dijo ferba es la manera más lógica de proceder, bueno al menos la que el sentido común dictaría, pero tambien es cierto que no es la mejor, por ejemplo una experiencia personal.
Un día se me ocurrió lanzarme a la aventura de viajar de Guadalajara México a Manzanillo (puerto), por el simple hecho de olvidarme de una chica, sin dinero ni ánimos decidí irme de aventón; gran aventura, conocí gente muy pintoresca, lugares extraños, -un mini cementerio de avionetas, vagones de trenes abandonados, caminos desiertos y pueblos casi fantasmas-, yo iba aplicando una especie de variable de este algoritmo, lo que me resulte mejor -un aventon al siguiente poblado o quedarme parado, el aventon; un aventon al siguiente entronque o quedarme parado, el aventon...- y con esto un viaje de 4 hrs en camión de pasajeros se volvieron 2 días. ¿por qué? en este caso simple, la mejor opción era acercarme aunque fuera poco, y quien se paraba era el tráfico local, así que fui de pueblo en pueblo -moverme poco era mejor que nada-. ¡Qué gran recuerdo!
Buen artículo, de cómo se explica el conocimiento empírico.
Me gusta la simplicidad de fondo que tiene este algoritmo. No hay preambulos sino que se va directo hacia el mejor trozo del pastel. Una sencillez genial.
Es genial... nunca lo había escuchado por ese nombre. Y no es tanto que sea un intensivo de algoritmos pero de perdido les puedo mencionar tres o cuatro que funcionan por conceptos similares.
Pero en lugar de entrar en detalles les planteo otro problema de estos que la naturaleza resuelve zepetillones de veces al día: ¿cómo sabe un haz de luz en qué dirección avanzar? ¡Cómo sabe qué par de trayectorias rectilíneas le toma menos tiempo para llegar desde un punto en el medio A hasta otro en el medio B?
La respuesta, un tanto metafísica, suele basarse en un principio. "Hay que minimizar la acción" y en términos de integrales de trayectoria vienes y deduces la Ley de Snell. Pero ¿no es aún más elegante, por no decir correcto, observar que en cada momento hay una trayectoria que minimiza su funcional de energía? Punto a punto los paquetes de energía interaccionan con el medio y el desplazamiento observado es hacia donde la energía se transfiere con menor dificultad.
A lo mejor parece ser la misma gata, pero le quitas a la metafísica un paso del porqué y le das un cómo. Lo siento si no lo expliqué bien, mis clases fueron hace mucho... por cierto, buen artículo.
Se parece más bien a una fórmula de lógica.
la distancia mas corta entre 2 puntos es una recta y san se acabó, para que dar tantas vueltas digo yo!!
Mejor pensar todo en objetos:
public abstract void ResolverProblema();
// TODO: buscar programador junior que lo implemente desde aca...
Al que me pregunto si hay que pagar 23 pesos, yo programe ese para esa cantidad, sino hay que usar variables y el codigo seria un poco mas largo ja...
Tal y como lo recuerdo yo de la universidad, y corregidme si me equivoco, un algoritmo voraz es aquel que ofrece una solución no necesariamente óptima compuesta por un conjunto de soluciones parciales, de manera que, en cuanto el algoritmo se decide por añadir una cierta solución parcial, nunca vuelve atrás. Hay ciertos problemas que cumplen el principio de optimalidad, es decir, que una solución óptima al problema está compuesta por soluciones parciales óptimas (en el caso mencionado arriba, una solución parcial óptima seria ir de una determinada ciudad a su vecina mas próxima), aunque no suele ser así.
Donde si que se utilizan mucho los algoritmos greedy es en búsquedas de tipo heurístico. Para que se hagan una idea, para un determinado problema se obtiene una solución voraz que no sea óptima pero "que sea bastante buena" y se toma como punto de partida para buscar soluciones mejores de forma mas exhaustiva a su alrededor. O sinó, al menos en el trabajo las usamos así
Si tenemos 1 billete de $50, 3 de $20 y 10 de $1, y quisieramos pagar $60 el algoritmo no nos daría la mejor opción. Tomaría el billete de $50 y los 10 de $1, pudiendo tomar los 2 de 20. Como se comentó antes, el algoritmo no siempre nos da la mejor solución.
Saludos.
en vez de gastar tanta energia y tiempo en ese algoritmo desarrollen la teletransportacion :D
:o excelente.... vi programacion el semestre pasado y gracias a eso me es facil comprender las utilidades de un algoritmo de este tipo
En mis días de Universidad recuerdo que, como parte de un curso, se abordó este problema utilizando distintos algoritmos. Uno de los que me llamo la atención fue el de “Colonia de Hormigas”. Considerando que las hormigas son prácticamente ciegas, y, sin embargo, moviéndose prácticamente al azar, acaban encontrando el camino más corto entre la fuente de alimento y el nido es genial emular su comportamiento y la utilizando de feromonas que refuerzan en cada iteración los caminos más óptimos y así al cabo de un tiempo obtener una ruta sólida.
Debes iniciar sesión para publicar un comentario.