Algoritmo de backtracking

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 programmingproblem» (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.

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.

Algo de código

Backtracking

package com.apascualco.algoritmos.backtracking;

import java.util.List;
import java.util.stream.IntStream;

public class Backtracking {

    public Pair<Integer, Integer> search(
            final List<Pair<Integer, Integer>> range,
            final Heuristics heuristics
    ) {
        int[] initialState = {0,0};
        final Pair<Integer,Integer> optimal = Pair.with(0,0);
        return this.search(initialState, range, optimal, 0,heuristics);
    }

    private Pair<Integer,Integer> search(
            final int[] state,
            final List<Pair<Integer, Integer>> range,
            final Pair<Integer,Integer> optimal,
            final int branch,
            final Heuristics heuristics
            ) {

        int rangeFrom = range.get(branch).getFirst();
        int rangeTo = range.get(branch).getSecond();

        IntStream.range(rangeFrom,rangeTo).forEach(cursor -> {
                    state[branch] = cursor;
                    if (heuristics.getPruning().test(state)) {
                        if (branch < state.length - 1) {
                            optimal.update(this.search(
                                    state.clone(),
                                    range,
                                    optimal,
                                    branch + 1,
                                    heuristics)
                            );
                        } else if (heuristics.getHeuristic().test(state, optimal)) {
                            optimal.update(Pair.with(state[0], state[1]));
                        }
                    }
                }
        );
        return optimal;
    }
}

Heuristics

package com.apascualco.algoritmos.backtracking;

import java.util.function.BiPredicate;
import java.util.function.Predicate;

public class Heuristics {

    private Predicate<int[]> pruning;
    private BiPredicate<int[],Pair<Integer, Integer>> heuristic;

    @SuppressWarnings("unused")
    private Heuristics() { }

    public Heuristics(final Predicate<int[]> pruning,final BiPredicate<int[], Pair<Integer, Integer>> heuristic) {
        this.pruning = pruning;
        this.heuristic = heuristic;
    }

    public static Heuristics of(final Predicate<int[]> pruning, final BiPredicate<int[],Pair<Integer, Integer>> heuristic) {
        return new Heuristics(pruning,heuristic);
    }

    public Predicate<int[]> getPruning() {
        return pruning;
    }

    public BiPredicate<int[], Pair<Integer, Integer>> getHeuristic() {
        return heuristic;
    }

}

Pair

package com.apascualco.algoritmos.backtracking;

public class Pair<A,B> {

    private A first;
    private B second;

    private Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }

    public void update(Pair<A, B> pair) {
        this.first = pair.getFirst();
        this.second = pair.getSecond();
    }

    public static <A, B> Pair<A, B> with(A value0, B value1) {
        return new Pair<>(value0, value1);
    }

    public A getFirst() {
        return first;
    }

    public B getSecond() {
        return second;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "first=" + first +
                ", second=" + second +
                '}';
    }
}

Implementación