La programación lineal es una herramienta, como hemos visto, fantástica. Sin tener que resolver ningún algoritmo hemos sido capaces de crear un planificador de rutas que, visto por primera vez parece (y es) un problema monumental. Pero es que además, con nuestro planificador de rutas, tal y como lo hemos planteado, podemos resolver directamente (y con soluciones exactas) el problema del viajante (un problema muy importante del que sólo hay soluciones eficientes en forma aproximada). Basta con indicar que como mucho queremos estar en un checkpoint al día, que el número mínimo de días sea el mismo que el de checkpoints y que checkpoints no comunicados directamente tengan sus aristas fijadas a 0, pidiendo a nuestro planificador que nos de la ruta con menor distancia posible (y ésto, usando tal cual nuestra función "solveProblem"). ¿Entonces?, ¿lo hemos resuelto o no?, ¿debemos aprender programación lineal o no?, y lo más importante, ¿ha servido para algo esta serie ¡de ocho posts!?.
Programación general y declarativa
Nuestra solución es correcta. Funciona como se espera y resuelve el tipo de problemas planteados. Pero lo más importante que me gustaría destacar, es que hay infinidad de problemas, y que se nos presentan día a día, que admiten una representación muy similar a la que hemos desarrollado en la serie.
Por ejemplo, ordenar un conjunto se transforma a programación lineal con sólo fijar On,n variables con las restricciones de unicidad en el ordinal (Σ Oi,*=1) y monoticidad en los elementos seleccionados (Oi,* · e* <= Oi+1,* · e*).
Sí, sería genial no sólo no tener que resolver ningún algoritmo, sino que además, la enumeración de requisitos hace que estructurar "el código" sea mucho más fácil, porque si dichos requisitos son independientes (ej. que los días sean consecutivos es un requisito que nada tiene que ver con que la distancia total recorrida esté acotada), estarán completamente desacoplados en nuestra implementación (mientras que en algoritmos ad-hoc, toda la solución suele estar intrincadamente relacionada). Y por tanto, la complejidad de verificar, refactorizar y/o modificar nuestro "código" se reduce drásticamente.
La mala noticia
Si, he estado clamando las fantásticas ventajas de dicho modelo de programación pero, ¿porqué entonces no es tan popular?, ¿porqué no se usa de forma habitual?.
El gran problema de este modelo de programación es que actualmente no es eficiente; no existen algoritmos ni máquinas que puedan resolver eficientemente (es decir, con recursos {procesador, memoria, tiempo, ...} razonables) problemas arbitrariamente grandes.
En nuestro caso concreto, nuestro planificador bien puede ser capaz de planificar rutas en una determinada zona y si filtramos previamente el número de checkpoints y puntos de interés a analizar, podrá encontrar las soluciones en un tiempo razonable. Pero si aumentamos el número y, en función de las restricciones impuestas, el tiempo que deberá emplear superará en mucho lo razonable para ese problema, la prueba más evidente ya la hemos dado, podemos representar el problema del viajante y éste, sabemos que no puede resolverse eficientemente (exponencial en el mejor de los casos).
En muchos casos por tanto, aunque podamos representar fácilmente un problema mediante programación lineal, será necesario hacer un algoritmo ad-hoc. Por ejemplo, la ordenación presentada anteriormente tiene complejidad cuadrática (como mínimo O(n2)) cuando todos conocemos algoritmos con mucho mejor coste (ej. O(n log n)).
La buena noticia
La buena noticia es que aun así, existen muchos problemas que podemos resolver eficientemente, por ejemplo, aunque sea un problema de variables enteras, el reparto priorizado de unidades desde almacenes a sus destinos puede resolverse con programación lineal no entera y éste si tiene soluciones eficientes. También ocurre (como en nuestro planificador) que muchas instancias (datos de entrada) de nuestro problema serán lo suficientemente pequeños para que podamos resolverlos en tiempo razonable ¡con todas las ventajas de usar este modelo!.
El futuro
El futuro siempre es incierto, en 1956 se predijo que en 10 años habría fantásticas máquinas con una inteligencia artificial que hoy día, sabemos estamos lejos de alcanzar. La inmersión 3D es otra área que ha tenido muchos altibajos y que no termina de quedar resuelta.
Sin embargo, hoy día disponemos de algoritmos que reconocen a personas en las imágenes con mejor tasa de acierto que los humanos y la calidad gráfica en tiempo real disponible hoy día era algo impensable cuando se estrenó Tron en 1982.
¿Será la computación cuántica la vía para resolver eficientemente todos los problemas en NP?, ¿conseguirá D-Wave Systems crear tal máquina?.
Yo no se cuando, pero de lo que sí estoy seguro, es que cuando se logre, todos nuestros ordenadores tendrán, cual actual GPU (o el flamante Xeon Phi), un coprocesador que resolverá nuestros modelos declarativos y entonces, la "Requirement Programming" estará a la orden del día.
NOTA: actualmente (y siempre hasta donde yo se) no se sabe (ni se tienen indicios claros) de si la computación cuántica permitirá resolver (de forma general) problemas en NP.
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)
En genbetadev | Programación declarativa: el superbuscador (VII)
