| navegación | |
Universidad del Cauca |
Contenido de la asignatura
En esta página puede consultar el contenido de la asignatura y alguna bibliografía asociada.
Las notas del examen final (3 corte) se encuentran en el siguiente enlace (HTML)
Algunos enlaces:
Enlace a libro digital: Técnicas de Diseño de Algoritmos Rosa Guerequeta y Antonio Vallecillo
[15-09-2009]Ejercicio de estudio. (Algoritmos voraces) Problema del viaje.
Un conductor de una empresa de mudanzas requiere llevar su carga desde una ciudad X hasta una ciudad Y. El camión que conduce le permite viajar máximo n kilómetros sin necesidad de parar en una estación de servicio para llenar el tanque nuevamente.
El conductor cuenta con un mapa vial, en el cual se le indica en kilómetros todas las estuaciones de servicio existentes entre la ciudad X y la ciudad Y. Debido a que la mudanza se debe entregar en el menor tiempo posible, el conductor desea hacer el mínimo número de paradas para tanquear su camión.
Diseñar un algoritmo voraz que dadas la distancias entre las estaciones de servicio que existen en la ruta y la cantidad de kilómetros que puede recorrer el camión con el tanque lleno, determine el mínimo número de paradas que debe realizar el conductor. Suponga que cada vez que el conductor para en una estación de servicio, llena completamente el tanque.