Seguimos con problemas que se pueden resolver mediante algoritmos voraces. Vamos imaginar que tenemos a una persona que desea viajar en coche desde un punto A hasta otro punto B (n kilómetros). El viajante dispone de un mapa de carretera que indica la distancia entre las gasolineras que están situadas en el trayecto que va a realizar. En el punto de origen, el tanque del coche se encuentra lleno. Conocemos un máximo de kilómetros que el coche puede realizar sin la necesidad de repostar (x kilómetros / xsu objetivo es pararse a repostar el menor número de veces posibles. El algoritmo voraz nos determinará en qué gasolineras el viajante tiene que parar a repostar.
Veamos el problema con un ejemplo:
En este ejemplo el viajante tiene que realizar un trayecto de 56 km. En su ruta dispone de 5 gasolineras, siendo conocedor de sus distancias entre ellas (vector g[i]). El número de kilómetros máximos que puede realizar sin repostar es 30, por lo tanto repostamos en una gasolinera si no podemos llegar a la siguiente. Si el viajante del problema avanza hasta la primera gasolinera se encuentra con lo siguiente:
Vemos que no es necesario repostar puesto que podríamos llegar a la siguiente gasolinera sin problemas. Esto no ocurre cuando llegamos a la tercera gasolinera:
Aquí calculamos los kilómetros que tendríamos que realizar para llegar a la siguiente gasolinera y nos indica que no poseemos suficiente combustible. Por lo tanto, debemos de repostar en la tercera gasolinera. Cabe decir que cuando repostamos los kilómetros que hemos realizado desde la última vez que repostamos (kms) vuelven a 0.
El mejor caso posible (que no tuviéramos que parar a repostar en ninguna gasolinera) tendríamos que recorrer el vector una sola vez, por lo que la complejidad sería O(n). El peor de los casos evidentemente sería tener que parar en todas las gasolineras, por lo cual tendríamos una complejidad O(n2). Así pues, la complejidad de este algoritmo se encuentra en un punto intermedio entre O(n) y 0(n2), según el número de gasolineras donde haya que parar.
Más información | Algoritmos Voraces en Wikipedia
Ver 6 comentarios