0

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.

1 respuesta 1

0

Si ya tienes la implementación bien hecha, lo tienes casi todo !

La BFS es el algoritmo que estas usando para encontrar la solución, una vez encontrada y teniendo la representación del árbol con sus nodos solo tienes que subir hasta la raíz (a través de los nodos padres).

Ejemplo, buscamos el nodo D:

    A       
   / \ 
  B   C
 / \   
D   E

Nodos visitados: A,B,C,D (encontrado!)

Lo que quieres saber ahora es como llegar desde A (estado inicial) a D (estado final), es decir, el recorrido A-B-D. A la hora de implementarlo, puedes visitar los nodos padres del estado final hasta llegar a la raíz, el resultado será el inverso de este recorrido.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.