En el post anterior aprendimos a representar relaciones lógicas con los objetos de nuestro sistema y conseguimos especificar (que no resolver) que una solución será válida si todos los días del viaje son elegidos consecutivos. En este post, resolveremos las últimas restricciones, que son las relacionadas con las distancias que tendremos que recorrer en nuestra ruta, ¡pero mucho ojo!, éste problema es *mucho* más complicado que aquel resuelto por Dijkstra...
Por último, fijaremos el criterio de optimización que permitirá al usuario indicar sobre qué características de la ruta desea priorizar y con ésto, habremos resuelto todos los requisitos que nos propusimos en el desafío.
Distancias
Nuestro planificador, considera las distancias que deben recorrerse entre checkpoints, por tanto y sin pérdida de generalidad, podíamos suponer que ya conocíamos las distancias más cortas que recorreremos para ir desde un determinado checkpoint de origen a otro de destino (bien usando nuestra modestísima función distance del ya lejano tercer post de la serie, bien usando el ingenioso algoritmo de Dijkstra o, si el tamaño de nuestro problema lo permite, el siempre increíble algoritmo Floyd-Warshall).
Pero claro, nuestro problema no consiste en encontrar la ruta más corta posible (para ello tenemos los algoritmos anteriores), ¡también debe poder encontrar la ruta más larga! (nuestro usuario puede querer hacer los más kilómetros posibles dentro del rango que él ha marcado), pero es que además, bajo cualesquiera otra de las restricciones impuestas (días consecutivos, número de puntos de interés deseado, etc...).
Representando caminos
Hasta ahora hemos tenido en consideración los checkpoints de nuestro problema pero, para poder contabilizar las distancias, debemos poder trabajar con los caminos que nos llevarán de unos a otros, es decir, las aristas o arcos de nuestro mapa de carreteras.
¿Cuantos desplazamientos posibles podemos realizar entre todos nuestros checkpoints?, si te acuerdas del raído y destartalado mapa de carreteras que siempre llevaban nuestros padres "en algún sitio" en el coche, sabrás la respuesta.
Obvio, pero es que además, como podemos permanecer en el mismo checkpoint, en la diagonal tendremos distancias válidas (0 km).
Se hace evidente por tanto que, cada una de esas celdas, corresponde con una nueva variable en nuestro problema las "aristas entre checkpoints que serán recorridas" que denominaremos E y cuyo índice son, para cada día (de salida), el checkpoint de origen y el checkpoint de destino (¡al día siguiente!), algo como ésto:
Así, si el primer día no viajamos (no salimos), ninguna de estas variables para el primer día será 1, si el segundo día viajamos del checkpoint 1 al 2 (¡en el que estaremos el tercer día!), entonces E2,1,2=1. Declarar nuestras variables E en F# puede ser así:
Si pero, ¿y cómo fijamos el valor que debe tener cada variable Ed,a,b?, bueno, puesto que una arista es seleccionada si parte del checkpoint a (el día d) y llega al checkpoint b (¡el día d + 1!), es porque ambas están seleccionadas y, al revés, si alguno de los checkpoints (de salida o llegada) no está seleccionado, entonces la arista no está seleccionada. Espera... ¡un AND!, resulta que nuestras variables están ligadas por la identidad Ed,a,b = Cd,a AND Cd+1,b.
Por tanto, para poder fijar nuestras variables E debemos establecer las siguientes restricciones (que es un AND como fijamos en el post anterior):
(La representación en F# la incluimos después con otras).
Restricción 10: la distancia recorrida para ir de un checkpoint al siguiente está acotada
Con las aristas que van a ser seleccionadas, podemos fijar restricciones, como aquella que permita a los usuarios indicar las distancias mínimas y máximas que están dispuestos a recorrer para ir, cada día, de un checkpoint al siguiente en la ruta. Fijar dicha restricción es crear únicamente una ecuación para cada arista (aristas en el espacio-tiempo, pues dependen del día de salida):
Si esa arista no es seleccionada, la primera y segunda ecuación se cumplen trivialmente, pues cualquier norma es no negativa. Y en caso de ser seleccionada, lo será porque cumple la acotación impuesta.
En F# podemos representar fácilmente tanto la ligadura AND como la restricción anterior:
Restricción 11: la distancia total de la ruta está acotada
Lógicamente, tan sólo tenemos que sumar todas las distancias de todas las aristas (seleccionadas) y acotar con las preferencias del usuario:
Y en F#:
Criterio de priorización de rutas
Hace algunos post, comentábamos la necesidad de que el usuario pudiera indicar sobre qué elementos estaba más interesado (precio económico, cortas distancias, muchos puntos de interés, etc...), pero queríamos hacerlo sin que ello afectara a todas las restricciones que hemos establecido anteriormente.
Afortunadamente, nuestra representación de las soluciones mediante un sistema de programación lineal nos permite fácilmente poder ajustar (balancear, priorizar, ...) los criterios disponibles (eso sí, como combinación lineal).
A modo de ejemplo, nosotros definimos los parámetros de ajuste: PriceImportance, DistanceImportance e IPNumberImportance (pero podrían ser muchos otros), los cuales pueden tomar cualquier valor real (incluso negativos, para invertir la importancia).
Entonces, la función a optimizar (daría igual máximizar que minimizar puesto que los valores de ajuste permiten invertir el sentido) sería:
Lógicamente las constantes de ponderación no están normalizadas, pero esa normalización puede depender del tipo de interface de usuario que finalmente se decida para establecer esos parámetros (por ejemplo como un triángulo en el que el usuario fija más cerca de un vértice u otro según importancia) y se calcularían en base a los valores de acotación o máximos posibles (casos de no estar acotados).
En F#, se establecería así:
En fin, al final, han sido únicamente 11 restricciones y cuyo algoritmo queda implementado en tan sólo 90 líneas de código F#, el código completo que puedes ejecutar lo tienes en este gist. El problema, que inicialmente nos parecía realmente complicado, lo hemos podido resolver de forma simple y muy concisa (aunque la serie haya quedado larga con el fin de explicar detalladamente cada restricción) y lo más importante, no hay elementos complicados o que requieran de un conocimiento profundo de las matemáticas que finalmente resuelven el problema, quizás si algo de práctica para sentirse cómodo "definiendo requisitos/restricciones", pero todo lo que merece la pena, requiere un poco de esfuerzo.
De todos modos, aún no hemos terminado la serie, puesto que en el próximo post, veremos hasta que punto podemos aplicar esta estrategia a otros problemas, el desempeño que tiene, porqué efectivamente es un lenguaje declarativo (si es que no ha quedado claro ya) y... ¿adivinarías cual será la imagen que encabezará el último post?.
(Restricciones adicionales)
La serie sólo pretende mostrar, con un ejemplo más o menos vistoso, la potencia de la programación lineal (entera en este caso); es por ello que los requisitos, y por tanto las restricciones implementadas, han sido elegidas con poco criterio práctico. Es probable por tanto, que te hayas preguntado porqué determinada restricción o restricciones no ha sido mostradas y como se representarían. Que puedan fijarse "los checkpoints inicial y/o final", que "el precio de la gasolina sea considerada en el precio", que incluso "se recomienden gasolineras más baratas" y muchos otros criterios pueden añadirse de forma independiente a nuestro planificador. Puedes pensar sobre cómo se representan éstos u otros requisitos y, si tenemos dudas ¡a los comentarios!.
Más información |
En genbetadev | Programación declarativa: el superbuscador (I)
En genbetadev | Programación declarativa: el superbuscador (II)
En genbetadev | Programación declarativa: el superbuscador (III)
En genbetadev | Programación declarativa: el superbuscador (IV)
En genbetadev | Programación declarativa: el superbuscador (V)
En genbetadev | Programación declarativa: el superbuscador (VI)
