Hace unos post, subí la implementación de una Búsqueda de coste uniforme (BCU) y expliqué, más o menos cómo funcionaba. Estaría bien que repasarais este post, ya que los cambios, de implementación en el ejemplo, tan sólo cambia la «comparación«, donde se evalúan los nodos.
Para entender el algoritmo A*, debemos pensar en el resultado de una función, con la suma entre el coste del nodo y la heurística que es calculado, desde el nodo actual hasta el nodo destino, lo podemos expresar como f(n) = g(n) + h'(n).
- Donde f(n) es el resultado o peso del nodo a evaluar.
- g(n) sería el coste de la arista
- h'(n) la heurística que hace una estimación del nodo actual hasta el destino
Si pensamos en la Búsqueda de coste uniforme (BCU), la podríamos definir, como un tipo de algoritmo b ya que f(n) = g(n) + 0, puesto que no tiene función heurística, se podría considerar 0 el resultado.
Me resulta fascinante, como la base algorítmica evoluciona en base la heurística, siendo siempre o prácticamente siempre, él mismo algoritmo con una función nueva de evaluación.
Nos basaremos en los mismos datos que en el post de Búsqueda de coste uniforme (BCU)
GRÁFO DE CONEXIÓN
CURIOSIDADES
private Comparator<NodeAStar> nodeAStarComparator(final City destination) {
return (o1, o2) -> {
final int costCity1 = o1.getCost();
final int heuristicValue1 = distance(o1.getCity().getCoords(), destination.getCoords()).intValue();
final int functionCity1Result = costCity1 + heuristicValue1;
final int costCity2 = o2.getCost();
final int heuristicValue2 = distance(o2.getCity().getCoords(), destination.getCoords()).intValue();
final int functionCity2Result = costCity2 + heuristicValue2;
return functionCity1Result - functionCity2Result;
};
}Si modificáis los valores, es curioso el comportamiento del algoritmo, os invito a que comparéis el BCU y A*, modificando los valores.
IMPLEMENTACION
