Después de hablar de la búsqueda en profundidad – Depth First Search (DFS) y también de búsqueda y funciones de evaluación heurística. Voy a traer a juntar el concepto de función heurística y el DFS, para crear, reproducir o explicar el algoritmo de backtraking, añadiendo una mejora sustancial al DFS.
INTRODUCCIÓN
En un post anterior escribí sobre la búsqueda y funciones de evaluación heurística, ahora es el momento de aplicar esta heurística, de manera más explicita, en el algoritmo de backtracking, para hacerlo más fácil, he separado el algoritmo y puesto nombres decentes para que cada parte se vea más clara.
En ciertas ocasiones nos encontramos con «integer programming problem» (Wikipedia). Cómo podéis leer en la wikipedia, son problemas de optimización y factibilidad matemática en los cuales una o varias variables son enteras y donde se aplican ciertas restricciones.
Por lo tanto en nuestro escenario, hablamos de un backtacking con poda (restricciones).
ESCENARIO
Por un momento, imaginamos que tenemos una fabrica de drones: terrestres y aéreos. Cómo hemos abierto hace poco, decidimos maximizar nuestros beneficios en la creación de los drones y aprovechar al máximo el tiempo que tenemos hasta la primera entrega.
| Aereo | Terrestre | |
| Horas | 10 | 6 |
| Piezas | 8 | 7 |
| Precio de venta | 68 | 58 |
| Coste total | 34 | 27 |
Lo primero que pensamos es en maximizar nuestros beneficios, el cual nos devolverá la heurística necesaria para resolver nuestro problema.
Basándonos en la tabla anterior tenemos que:
f(x,y) = (68-34)x+(58-27)y (donde x es un tipo de dron e y el otro. )
Después de haber resulto nuestro problema, planteando una ecuación, continuamos, exponiendo nuestras restricciones a la hora de la fabricación de estos productos.
Aunque creo que es auto explicativo, comentaremos un poco. Como el tiempo es finito. necesitamos saber la cantidad de horas nos quedan de trabajo hasta la entrega, en nuestro caso 240 horas.
Por otro lado, el material es finito y suponiendo que las piezas fueran abstractas y funcionaran en cualquier de los dos drones, tenemos otro límite, 230 piezas.
Y ese es el resultado, de las restricciones.
OBSERVACIONES DE LA IMPLEMENTACIÓN
Podríamos acotar el «rango» en la implementación, porque por ejemplo: si observamos el ejemplo de las restricciones, podemos deducir a simple vista que la (x) tiene un rango de valores de 0 a 24 y la (y) tiene un rango de valores de 0 a 32. Cosa que no hice, en la implementación, puse unos rangos aleatorios, cosa no muy interesante.
Se podría calcular el máximo del rango dividiendo el multiplicando de la x por el resultado en las dos ecuaciones y obtener el numero mas bajo entre los dos. Esto nos devolvería los valores máximos que pueden obtener cada una de nuestras incógnitas.
Aunque tengo intención de subir estos algoritmos en diferentes lenguajes de programación, la primera iteración, será en Java. Considero que puede ser un poco complejo, pero para cualquier duda no dudéis en contactar conmigo, el email es gratuito.
IMPLEMENTACIÓN
