Estoy resolviendo el problema del granjero en IA, actualmente ya realizo la búsqueda en Anchura correctamente, pero quiero obtener el camino más corto a partir de las soluciones encontradas.
Este es mi código de la búsqueda BFS:
private ArrayList<Nodo> solutions;
private Nodo root;
public void BFS(Estado estadoInicial, Estado estadoFinal) {
Queue<Nodo> abiertos = new LinkedList<>();
solutions = new ArrayList<>();
root = new Nodo(estadoInicial);
root.nivelProfundidad = 0;
abiertos.add(root);
while (!abiertos.isEmpty()) {
Nodo n = abiertos.poll();
List<Estado> sucesores = n.datosEstado.getEstadosSucesores();
for (Estado estado : sucesores) {
Nodo hijo = new Nodo(estado);
hijo.nodoPadre = n;
hijo.nivelProfundidad = n.nivelProfundidad + 1;
if (!hijo.esRepetido()) {
n.nodosHijos.add(hijo);
if (hijo.datosEstado.esEstadoSolucion(estadoFinal) == false) {
abiertos.add(hijo);
} else {
solutions.add(hijo);
}
}
}
}
}
Teorizo que es a partir de recorrer los nodos padres; esta es mi clase Nodo:
public class Nodo {
public Nodo nodoPadre;
public Estado datosEstado;
public ArrayList<Nodo> nodosHijos;
public int nivelProfundidad;
public Nodo(Estado datosNodo) {
this.nodoPadre = null;
this.datosEstado = datosNodo;
this.nodosHijos = new ArrayList<>();
this.nivelProfundidad = 0;
}
//Buscar estados repetidos
public boolean esRepetido() {
}
Solo debe haber una solución, gracias, quedo al pendiente.