BusquedaA

package agentesIA;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;

public class BusquedaA {
    private Nodo nodoInicial;
    private Nodo nodoObjetivo;
    private List<Nodo> visitados;
    private List<Nodo> frontera = new ArrayList<Nodo>();

    public BusquedaA() {
        this.addNodos();
    }

    public Nodo busqueda() {
        frontera.add(this.nodoInicial);
        Nodo nodoActual;
        int costeActual;
        int i;

        while(!frontera.isEmpty()) {
            Collections.sort(frontera); // Super ineficiente, pensar luego como implementar
                                        // una cola de prioridad actualizable
            nodoActual = frontera.remove(0);

            if(nodoActual.equals(nodoObjetivo)) { return nodoActual; }

            Set<Nodo> hijos = nodoActual.getHijos();

            for(Nodo hijo: hijos) {
                costeActual = nodoActual.getCosteHijo(hijo);

                i = visitados.indexOf(hijo);
                if(i != -1 && visitados.get(i).coste < costeActual) {
                    continue;
                }
                visitados.remove(hijo);

                i = frontera.indexOf(hijo);
                if(i != -1 && frontera.get(i).coste < costeActual) {
                    continue;
                }
                frontera.remove(hijo);

                hijo.coste = costeActual;
                hijo.padre = nodoActual;
                frontera.add(hijo);
            }

            visitados.add(nodoActual);
        }

        return null; // No encontrado
    }

    public void mostrarCamino(Nodo nodo) {
        if(nodo.padre != null) {
            mostrarCamino(nodo.padre);
        }
        System.out.println(nodo);
    }

    private void addNodos() {
        Nodo ushuaia = Nodo.crearNodo("Ushuaia", 3152);
        Nodo tucuman = Nodo.crearNodo("Tucuman", 0);
        Nodo sanLuis = Nodo.crearNodo("San Luis", 730);
        Nodo rioGallegos = Nodo.crearNodo("Rio Gallegos", 2780);
        Nodo rosario = Nodo.crearNodo("Rosario", 813);
        Nodo neuquen = Nodo.crearNodo("Neuquen", 1386);
        Nodo mendoza = Nodo.crearNodo("Mendoza", 764);
        Nodo cordoba = Nodo.crearNodo("Cordoba", 525);
        Nodo buenosAires = Nodo.crearNodo("Buenos Aires", 1085);
        Nodo comodoroRivadavia = Nodo.crearNodo("Comodoro Rivadavia", 2088);
        Nodo salta = Nodo.crearNodo("Salta", 226);

        ushuaia.addHijo(rioGallegos, 580);

        tucuman.addHijo(mendoza, 955);
        tucuman.addHijo(cordoba, 565);
        tucuman.addHijo(buenosAires, 1251);

        sanLuis.addHijo(neuquen, 770);
        sanLuis.addHijo(cordoba, 428);
        sanLuis.addHijo(buenosAires, 830);

        rioGallegos.addHijo(comodoroRivadavia, 778);
        rioGallegos.addHijo(ushuaia, 580);

        rosario.addHijo(cordoba, 405);
        rosario.addHijo(buenosAires, 298);

        neuquen.addHijo(sanLuis, 770);

        mendoza.addHijo(cordoba, 638);
        mendoza.addHijo(tucuman, 955);

        cordoba.addHijo(mendoza, 638);
        cordoba.addHijo(tucuman, 565);
        cordoba.addHijo(rosario, 405);
        cordoba.addHijo(buenosAires, 695);
        cordoba.addHijo(sanLuis, 428);

        buenosAires.addHijo(sanLuis, 830);
        buenosAires.addHijo(cordoba, 695);
        buenosAires.addHijo(tucuman, 1251);
        buenosAires.addHijo(rosario, 298);
        buenosAires.addHijo(salta, 1462);

        comodoroRivadavia.addHijo(rioGallegos, 778);
        comodoroRivadavia.addHijo(sanLuis, 1745);
        comodoroRivadavia.addHijo(buenosAires, 1761);

        salta.addHijo(tucuman, 306);
        salta.addHijo(buenosAires, 1462);

        this.nodoInicial = comodoroRivadavia;
        this.nodoObjetivo = tucuman;
    }

    public void main() {
        BusquedaA a = new BusquedaA();
        Nodo f = a.busqueda();
        if(f != null) {
            a.mostrarCamino(f);
        } else {
            System.out.println("No se ha encontrado un camino");
        }
    }
}