Algoritmo A* en Java

Aqui teneis la codificacion en Java de uno de los algoritmos de Busqueda de Camino mas usados en Inteligencia Artificial


Java A* Algorithm
=================

// -*- mode: java; folded-file: t -*-
/*
* Author Geert-Jan van Opdorp
*
* Copyright (c) 1995 AI Engineering.
*
*/
package aie.astar;
// {{{ import

import java.awt.*;
import java.awt.image.*;
import java.net.*;
import java.applet.*;
import java.lang.*;
import java.util.*;

// }}}

// {{{ final class node

final class node {
  State state;
  int costs;
  int distance;
  int total;
  node parent;
  node(State theState, node theParent,  int theCosts, int theDistance) {
    state = theState;
    parent = theParent;
    costs = theCosts;
    distance = theDistance;
    total = theCosts + theDistance;
  };
}


// }}}
// {{{ public final class AStar

public final class AStar {
  // {{{ Variables

  private final  Hashtable open = new Hashtable(500);
  private final  Hashtable closed = new Hashtable(500);
  public int evaluated = 0;
  public  int expanded = 0;
  public int bestTotal = 0;
  public boolean ready = false;
  private  boolean newBest = false;
  private final  Vector nodes = new Vector(); //sorted open node

  // }}}

  private  synchronized void setBest (int value) {
    bestTotal = value;
    newBest = true;
    notify(); // All?
    Thread.currentThread().yield();  //for getNewBest
  }

  public  synchronized int getNewBest() {
    while(!newBest) {
      try {
wait();
      } catch (InterruptedException e) {
      }
    }
    newBest = false;
    return bestTotal;
  }
 
// {{{ private  node search()

  private  node search() {
    node best;
    Vector childStates;
    int childCosts;
    Vector children = new Vector();
   
    while (!(nodes.isEmpty())) {
      best = (node) nodes.firstElement();
       if(closed.get(best.state) != null) { //to avoid having to remove
nodes.removeElementAt(0);          // improved nodes from nodes
continue;
       }
      if (!(best.total == bestTotal)) {
        setBest(best.total);
      }
      if ((best.state).goalp()) return best;

      children.removeAllElements();
      childStates = (best.state).generateChildren();
      childCosts = 1 + best.costs;
      expanded++;

      for (int i = 0; i < childStates.size(); i++) {
State childState = (State) childStates.elementAt(i);
node closedNode = null;
node openNode = null;
node theNode = null;

if ((closedNode = (node) closed.get(childState)) == null)
  openNode = (node) open.get(childState);
theNode = (openNode != null) ? openNode : closedNode;
if (theNode != null) {
  if (childCosts < theNode.costs) {
    if (closedNode != null) {       
      open.put(childState, theNode);
      closed.remove(childState);
    } else {
      int dist = theNode.distance;
      theNode = new node(childState, best, childCosts, dist);
      open.put(childState, theNode);
       //nodes.removeElement(theNode); //get rid of this
    }
    theNode.costs = childCosts;
    theNode.total = theNode.costs + theNode.distance;
    theNode.parent = best;
    children.addElement(theNode);
   
  }
} else {
  int estimation;
  node newNode;

  estimation = childState.estimate();
  newNode = new node(childState, best, childCosts, estimation);
  open.put(childState, newNode);
  evaluated++;
  children.addElement(newNode);
}
      }
      open.remove(best.state);
      closed.put(best.state, best);
      nodes.removeElementAt(0);
      addToNodes(children); // update nodes
     
    }
    return null; //no open nodes and no solution
  }

// }}}

  private int rbsearch(int l, int h, int tot, int costs){
    if(l>h) return l; //insert before l
    int cur = (l+h)/2;
    int ot = ((node) nodes.elementAt(cur)).total;
    if((tot < ot) ||
       (tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
      return rbsearch(l, cur-1, tot, costs);
    return rbsearch(cur+1, h, tot, costs);
  }

  private int bsearch(int l, int h, int tot, int costs){
    int lo = l;
    int hi = h;
    while(lo<=hi) {
      int cur = (lo+hi)/2;
      int ot = ((node) nodes.elementAt(cur)).total;
      if((tot < ot) ||
(tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
hi = cur - 1;
      else
lo = cur + 1;
    }
    return lo; //insert before lo
  }
     

// {{{ private  void addToNodes(Vector children)

  private  void addToNodes(Vector children) {
    for (int i = 0; i < children.size(); i++) {
      node newNode = (node) children.elementAt(i);
      int newTotal = newNode.total;
      int newCosts = newNode.costs;
      boolean done = false;
      int idx = bsearch(0, nodes.size()-1, newTotal, newCosts);
      nodes.insertElementAt(newNode, idx);
   
//       for (int j = 0; j < nodes.size(); j++) {
// int ot = ((node) nodes.elementAt(j)).total;
// if (newTotal <  ot) {
//   nodes.insertElementAt(newNode, j);
//   done = true;
//   break;
// }
// if (newTotal == ot) {
//   if (newNode.costs >= ((node) nodes.elementAt(j)).costs) {
//     nodes.insertElementAt(newNode, j);
//     done = true;
//     break;
//   }}
//       }
//       if (!done) nodes.addElement(newNode);
    }
  }

// }}}
// {{{ public final  Vector solve (State initialState)

  public final  Vector solve (State initialState) {
    node solution;
    node firstNode;
    int estimation;
   
    expanded = 0;
    evaluated = 1;
    estimation = initialState.estimate();
    firstNode = new node(initialState, null, 0, estimation);

    open.put(initialState, firstNode);
    nodes.addElement(firstNode);

    solution = search();
    nodes.removeAllElements();
    open.clear();
    closed.clear();
    ready = true;
    setBest(bestTotal);
    return getSequence(solution);
  }

// }}}
// {{{ private  Vector getSequence(node n)

  private  Vector getSequence(node n) {
    Vector result;
    if (n == null) {
      result = new Vector();
    } else {
      result = getSequence (n.parent);
      result.addElement(n.state);
    }
    return result;
  }

// }}}
}

// }}}

State package
=============

// -*- mode: java; folded-file: t -*-
package aie.astar;
import java.util.Vector;
// {{{ abstract class state

public abstract class State {
  public abstract Vector generateChildren();
  public abstract boolean goalp();
  public abstract int estimate();
}

// }}}

11 opiniones en “Algoritmo A* en Java”

  1. El problema de los profesores universitarios es que no viven en el mundo real. Para empezar creen que por el hecho de ser profesor universitario es Dios. Y nada más lejos de la realidad. Me gustaría a mi verlos en el mundo real de las empresas. ¿Qué iban a solicitarles a los desarrolladores? ¿Qué no reutilizaran código, porque es ‘copiar’? ¿Qué no usen propiedades en los objetos tipo .sort() sino que implementen el algoritmo shell o quicksort cada vez (y sin copiar?
    Pobres incimpetentes.

  2. ahi quedo el tema, osea no tuve notificiacion alguna pero me consta que algunos compañeros de la universidad han agradecido este post, supongo que lo habran incluido en el sistema ANTICOPIAS, aunque siempre he dudado de su existencia , para mi que tienen un simple comparador de textos 😉 .
    en mi caso cada vez me doy cuenta que vale menos la pena acabar la ingenieria superior y mas en experimentar por mi mismo.

  3. Hola! supongo hace mil años publicaste esto, pero te comento que el articulo del que brindaste un link (policyalmanac) está super interesante y bien útil! Muchas gracias! por cierto: en que terminó lo del profesor?

  4. hola alfonso, me ha gustado lee tu comentario y soy de tu misma opinion, no me preocupa que me suspenda o no es mas no me pueden suspender puesto que no he presentado la practica, por falta de tiempo mi actividad laboral me lo impidio, por lo que es otro argumento a mis comentarios puesto que si teniendo la implementacion del algoritmo no me dio tiempo a acabar la practica significa que esta dentro del 15% de la misma que yo presupungo, mi indignacion no es por mi si no por mis compañeros y mas los de la nueva hornada los que llevamos mucho tiempo en el ambito laboral profesional y en el universitario (en mi caso terminando mi segunda carrera) me preocupa mas bien poco ese tipo de comentarios, he conocido profesores muy buenos que me han ayudado en mis estudios y de los que realmente puedo decir que HE APRENDIDO y otros de los cuales me abstengo mis comentarios….

  5. Hola viper,

    Sólo quería dar mi opinión sobre el tema. Repito, lo que sigue es únicamente mi opinión y no pretende establecer una crítica ni dar juicios de valor más allá de mi propio criterio.
    – Sobre el comentario del profesor (si es que realmente es él y no algún graciosillo), simplemente decir que amenazar a un alumno por un post en su blog me parece de lo más rastrero. Y particularmente, un profesor (e investigador) en Inteligencia Artificial debería saber que el avance en esa ciencia se produce en gran parte debido a la disponibilidad de software para investigación, muchas veces libre, hecho gracias a esfuerzos particulares o dinero público (véanse Weka, Elvira, SMART, Lucene, …). Mal planteamiento que una práctica de Inteligencia artificial consista en la re-re-re-reimplementación de un algoritmo. ¿Cuántos millones de A* se implementan (innecesariamente) cada curso escolar en todas las universidades del mundo? ¿No sería mejor realizar un estudio numérico de diferentes heurísticas (admisibles y no admisibles)?
    – Sobre si la posibilidad de suspenderle se debe únicamente a la publicación de ese código, comentar que si ha sido publicado tras el plazo de entrega, como comenta el alumno, me parece una medida injustificada, y la sorna añadida le resta aún más (si cabe) autoridad.

    Un cordial saludo y suerte.

  6. suena a a amenaza yo creia que la carrera esta para aprender a pensar y saber desenvolvernos en el mundo laboral usando los algoritmos que ya existen y estan desarrollados por personas con mucha mas experiencia que nosotros, y no creo que se deba dar una practica como copia por usar esa implementación del algoritmo, de todas maneras para SEPTIEMBRE todos podeis usar el pseudodigo que teneis aqui:

    http://www.gameai.com/javastar.html

    o aqui

    http://www.policyalmanac.org/games/articulo1.htm

    por cierto el mismo algoritmo ha sido usado por distintas universidades como ejerccios de practicas pq usando bien los buscadores obtendreis toda la ayuda.

    que conste que en mi opinion la implementacion del algoritmo publicada es como mucho el 15 % de la practica, y ha sido publicada fuera de fechas.

    y como todos sabemos nunca repetis en septiembre la misma practica, asi que el tono amenzante esta de mas a mi entender.

    Un Saludo

  7. Hola,
    soy uno de los profesores de la asignatura Fundamentos de Inteligencia Artificial de la UA. Me guardo el enlace para futuras correcciones (Septiembre, sobre todo).

Deja un comentario