El problema de la diligencia fue elaborado especialmente para ilustrar las características e introducir la terminología de la programación dinámica. Trata sobre una cazafortunas mítico de Missouri que decide ir al oeste a unirse a la fiebre del oreo en California a mediados del siglo XIX. Tiene que hacer el viaje en diligencia a través de territorios sin ley cuando existían serios peligros de ser atacado por merodeadores. Aun cuando su punto de partida y su destino eran fijos, tenía muchas opciones en cuanto a qué estados (o territorios que más tarde se convirtieron en estados) debía elegir como puntos intermedios. En la figura 11.1 se muestran las rutas posibles, en donde cada estado está representado por un círculo numerado. Como se puede observar, se requerían cuatro etapas (jornadas en diligencia) para viajar desde su punto de partida en el estado A (Missouri) a su destino en el estado J (California).
Este cazafortunas era un hombre prudente que estaba preocupado por su seguridad. Después de reflexionar un poco se le ocurrió una manera bastante ingeniosa para determinar la ruta más segura. Se ofrecían pólizas de seguros de vida a los pasajeros. Como el costo de la póliza para cualquier jornada de la diligencia estaba basado en una evaluación cuidadosa de la seguridad del recorrido, la ruta más segura debía ser aquella que tuviera el costo total más barato.
El costo de la póliza estándar para el viaje en diligencia, del estado i al estado j, se denotará por cij, y es
La atención se centrará sobre la pregunta Cuál es la ruta que minimiza el costo total de la póliza?
No hay comentarios.:
Publicar un comentario