Programación declarativa: el superbuscador (II)

En el post anterior planteábamos un ambicioso desafío; crear un planificador de viaje que tenga en cuenta diversos tipos de preferencias para sugerir al usuario la mejor alternativa teniendo en cuenta la información disponible.

En este post, vamos a pensar sobre el tipo de problemas que guardan relación con éste, algunas de las alternativas (abstractas) de que disponemos hoy día para resolverlos y concretar el problema específico que finalmente dejaremos resuelto.

¿Te animas?

¿A que tipo de problema nos enfrentamos?

El tipo de problema que hemos planteado guarda relación con una enorme cantidad de problemas que se resuelven de forma similar, al ojo inexperto, pueden parecer problemas completamente diferentes, pero con un poco de práctica, podemos aprender a identificarlos y ¡resolverlos, no resolviéndolos!.

Pero también ocurre al contrario, existen muchos problemas que pueden parecer cercanos e incluso equivalentes (si resolvemos uno tenemos resuelto el otro) pero se trata en realidad de problemas con una dificultad en su resolución muy diferentes.

Pongamos un ejemplo.

El principio del palomar

El principio del palomar es algo bastante evidente, pero darle nombre ayuda a pensar y compartir ideas.

Informalmente el principio del palomar viene a decir que, si tenemos 10 palomas y sólo 8 nidales, es de perogrullo que al menos algún nido estará ocupado por más de una paloma.

Sabiendo ésto, supongamos que nos piden dos problemas diferentes:

• Determinar, para cierta ciudad con más de 200.000 habitantes si, al menos dos de ellos, tienen exactamente la misma cantidad de pelos en la cabeza.

• En las mismas condiciones, encontrar cualesquiera dos personas con, exactamente la misma cantidad de pelos en la cabeza.

Parecen problemas similares, pero resolverlos, conlleva dificultades enormemente diferentes. Por supuesto, si sabemos resolver el segundo problema, podremos resolver el primero, pero el primer problema se resuelve trivialmente con un "sí, hay al menos dos personas con exactamente la misma cantidad de pelos en la cabeza, pues la cantidad de pelos en la cabeza de un humano difícilmente superará los 200.000"; sin embargo, resolver el segundo problema, implica, como mínimo, tomar alguna medida a cada individuo.

Decisión, optimización o enumeración

Así, una forma de clasificar los problemas como el que nos ocupa, puede ser por el tipo de resultado que se solicita y ésto burdamente podría definirse así:

• Problemas de decisión: la única respuesta que se solicita es un Sí o un No, nada más. Son problemas, por lo común, tremendamente fáciles de resolver, pero tremendamente difíciles de resolver eficientemente.

• Problemas de optimización: no sólo se solicita conocer si existe o no solución, sino que se desea algunas de aquellas que tengan propiedades especiales (ej. el precio total sea el menor posible, la distancia total recorrida sea la mayor posible, etc...). Resolviendo éstos, obviamente resolvemos los de decisión (equivalentes). Normalmente también, es posible reducir estos problemas a otros de decisión de forma eficiente (pero claro, los anteriores no suelen ser fáciles).

• Problemas de enumeración: no sólo se solicita conocer alguna de las mejores soluciones, sino que se desea ¡obtener todas! (no necesariamente de forma literal, podría por ejemplo quererse obtener las N mejores soluciones). Sólo en algunas ocasiones (enumerar un conjunto es en general complicado) sabiendo solucionar los anteriores, podemos solucionar éstos también.

La clasificación anterior, aplicada a nuestro problema, nos lleva a que no nos bastará con saber si existe una ruta que satisfaga nuestras preferencias ¡queremos un informe que nos la detalle!, así, podemos ya asegurar que se trata de los segundos tipos de problemas.

Super-resultado o super-resultados

Como con los pelos en la cabeza, la "sutil" diferencia de obtener "sólo una" o varias de las mejores rutas que harán de nuestras vacaciones un camino de rosas, supone un abismo enorme en la dificultad que conlleva. ¿Por qué?.

Bueno, hay dos problemas principalmente, el primero trata sobre la propia definición de "alternativa" pues, si mi alternativa a un viaje de 5 días es repostar dos kilómetros más allá... vaya alternativa ¿no?. Dar varias alternativas al usuario es "otra cosa" e informalmente significa que debe haber una diferencia cualitativa y cuantitativa (subjetivas ambas) entre las alternativas que se den.

Pero el mayor problema es que, sencillamente, nuestro poderoso lenguaje en el que implementaremos nuestro superbuscador sólo nos arroja una solución. Aun así, podemos resolver nuestro problema de enumeración en base al de optimización, un algoritmo para ello podría ser:

• Sea A el conjunto de alternativas (inicialmente vacío)
• Buscar la mejor alternativa, aplicando restricciones de tal forma que únicamente se limiten (eliminen) las alternativas en A (y obviamente añadir al conjunto).
• Repetir [2] las veces necesarias.

Mientras obtenemos el conjunto A, podemos establecer una métrica sobre él (el "gusto" del usuario), y mostrar al usuario sólo aquellas alternativas "diferenciadoras y óptimas" (ej. una forma sencilla es hacer clustering con dicha métrica y mostrar la alternativa óptima de cada grupo obtenido).

Todo ésto, es bastante feo, complicado e ineficiente para total, mostrar al usuario varias alternativas que él en última instancia deberá valorar e igualmente volver a restringir si ninguna de ellas le satisface.

Así, para resolver nuestro buscador fantástico, parece que lo mejor es, simplemente, sugerir al usuario alguna de las mejores alternativas y que él añada restricciones sobre aquellos requisitos que él considera inválidos para refinar sus preferencias (ej. "no pasar por esa ciudad que ya la visité hace poco").

(En todo caso, si se impone como requisito, tendríamos la capacidad de implementarlo).

Lo que es óptimo para mi ¿es óptimo para ti?

Hemos llegado a la conclusión que debemos resolver un problema de optimización, ¿pero qué optimizamos?, ¿la distancia recorrida?, ¿el precio final?, ¿el número de noches?, ¿el número de noches mientras no salga "muy caro"?, etc...

Por supuesto no sería un superbuscador (y el nuestro lo será) si siempre nos devolviera resultados basados en un único criterio, ¿pero que criterios consideramos?.

En realidad, tenemos el mismo problema que con la definición de "alternativa", pero ¡ay!, el criterio de optimización no podemos ignorarlo, porque la mejor solución está dada precisamente por la importancia que el usuario da a cada uno de los factores a considerar (precio, distancia, tipo de eventos, ...).

En un algoritmo "ad-hoc" que resolviera nuestro problema, probablemente nuestro código debería considerar estas preferencias (ej. primero obtenga las rutas más cortas, luego elegir los puntos de interés por precio, luego ...), lo cual es un claro quebradero de cabeza. Afortunadamente, nuestro poderoso lenguaje, nos permite tratar de forma independiente la ordenación del conjunto de soluciones; es decir, podemos cambiar el orden en el que se buscan las soluciones, sin modificar el problema planteado.

Requisitos finales

Creo que las principales restricciones que pueden plantearse al problema están aclaradas: número de resultados y criterios de optimalidad. En el primer caso, podemos aportar cuantas alternativas sean necesarias, pero complica "innecesariamente" el problema y, en el segundo caso, nuestro algoritmo no puede estar obligado a obtener las soluciones óptimas por criterios fijos (ej. la distancia), sino que la optimalidad de cada solución debe poderse modificar sin que afecte al algoritmo general.

Lógicamente los detalles de unos hipotéticos requisitos influirán en el algoritmo final, yo voy a fijar aquí unos cuantos, sin detrimento que, el mismo algoritmo, funcionará igualmente con otra ingente cantidad de requisitos "similares" (también existen requisitos que lo invalidan, obviamente, como fijar una relación cuadrática entre distancia y precio), en cualquier caso, también buscamos que el problema concreto que vamos a resolver no sea demasiado complicado de seguir:

• Definimos "punto de interés" como un evento localizado geográfica y temporalmente (ej. "el concierto en directo de X grupo el día Y", "el restaurante X que cierra los lunes por descanso semanal", "la playa de X población", etc...) que además dispone de propiedades globales (ej. el precio) y propiedades de usuario (ej. la importancia que tienen para él, el nº mínimo de eventos que quiere disfrutar, etc...).

• Definimos un "checkpoint" como los puntos, zonas, poblaciones, etc... por las que podemos pasar y que contienen los puntos de interés disponibles (ej. en una ciudad puede haber playa y en otras no, un concierto para un día sólo ocurre en un sitio, etc...).

• Nuestro buscador, debe tomar los datos disponibles (los "punto de interés" y "checkpoint"), las preferencias de usuario y emitir un informe con la ruta y puntos de interés óptimos para sus criterios.

• Nuestro buscador debe poder obtener la mejor ruta priorizando cualquier criterio (o combinación de los mismos) sin modificar el propio algoritmo.

• Como ejemplos de preferencias que podrá fijar el usuario:

  </li>
</ul>

Implementación

Como muchos habréis imaginado (y apuntado en los comentarios y en twitter), ese poderoso lenguaje del que he estado hablando es la programación lineal de la que ya hablamos en el post Programación lineal y entera.

Lógicamente la "forma" final que tiene la solución ha estado en todo momento supeditada a las capacidades de dicha herramienta, aun así, hemos visto cómo podemos ampliar sus soluciones (en la enumeración de alternativas) y comprobado, que la cantidad de tipos de restricciones y relaciones que puede manejar es muy elevado. Piensa por un momento en el tipo de "cosas" que hay que controlar en el problema anterior (ej. de los 10 días que vamos a rastrear, debemos tomar entre 4 y 7, ¡pero consecutivos!, la ruta debe planificar todos los días desde que empezamos, hasta que terminamos el viaje).

¿Te animas a implementar tú mismo todas o alguna de las restricciones de nuestro problema?.

En el próximo post, veremos cómo se codifican en tan sorprendente lenguaje las diferentes restricciones (¡que no estrategias de solucionar!) que posee nuestro problema y piensa, que aunque nosotros trabajamos en un superbuscador de rutas, muchos de tus problemas admiten una formulación similar.

En Genbeta Dev | Programación declarativa