Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
Los algoritmos codiciosos son un tipo de algoritmo que toma la mejor decisión en cada paso para lograr el objetivo general. Por ejemplo, si el objetivo es encontrar la ruta más corta del punto A al punto B, un algoritmo voraz elegiría la ruta más corta en cada paso, sin tener en cuenta la longitud total de la ruta.
Uno de los ejemplos más famosos de un algoritmo codicioso es el problema del viajante de comercio. El objetivo de este problema es encontrar el camino más corto que visite cada ciudad exactamente una vez y regrese al punto de partida. Un enfoque ingenuo de este problema sería probar todos los caminos posibles y comparar las longitudes de cada uno. Sin embargo, esto es muy ineficiente y llevaría mucho tiempo ejecutarlo.
Un algoritmo codicioso, por otro lado, haría los siguientes pasos:
Los pasos anteriores siempre encontrarán un camino, pero puede que no sea el camino más corto posible. En algunos casos, es posible encontrar la solución óptima utilizando un algoritmo codicioso. En otros casos, no lo es.
Digamos que tenemos las siguientes ciudades y las distancias entre ellas:
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
Si usamos el algoritmo voraz descrito anteriormente, el camino tomado sería:
City 1 -> City 2 -> City 3 -> City 4 -> City 5 -> City 1
Que tiene una distancia total de:
0 + 100 + 200 + 300 + 400 + 0 = 1000km
Sin embargo, la ruta óptima sería:
City 1 -> City 5 -> City 4 -> City 3 -> City 2 -> City 1
Que tiene una distancia total de:
0 + 400 + 300 + 200 + 100 + 0 = 1000km
Como puede ver, el algoritmo codicioso no siempre encuentra la solución óptima. Sin embargo, suele ser mucho más rápido que otros algoritmos, como el enfoque de fuerza bruta, por lo que se suele utilizar en la práctica.
City 1: 0km
City 2: 10km
City 3: 15km
City 4: 20km
City 5: 25km
¿Cuál es el camino recorrido y la distancia total? ¿Es este el camino óptimo?
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
¿Cuál es el camino recorrido y la distancia total? ¿Es este el camino óptimo?
Pruebe con otros conjuntos de ciudades y distancias y vea qué camino toma el algoritmo. ¿Puedes encontrar un conjunto en el que el algoritmo no encuentre la ruta óptima?
Intenta mejorar el algoritmo para que siempre encuentre la ruta óptima.