Algoritmo A* en Java
11/13/2007Aqui 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();
}
// }}}
[…] de los post mas visitados de la web es sobre el algoritmo de A* en Java que escribí en mi época de la universidad, hoy se me ha ocurrido preguntarle a ChatGPT como lo haria el, aqui […]
… [Trackback]
[…] There you can find 60267 additional Info to that Topic: edadfutura.com/algoritmo-a-en-java/ […]
Como seria el void main, necesito este algoritmo para inteligencia artificial agradezco la ayuda
Hola Luis siento no poder ayudarte hace mucho tiempo que no toco este algoritmo
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.
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.
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?
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….
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.
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
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).