Hoy les comparto algunas implementaciones sobre búsqueda no informada en JAVA, usando un nuevo enfoque funcional, comentado todo en español, espero que les sea de ayuda a quien lo necesite Funciona con el JDK 10...


Terminología

    Node -> Una estructura de datos que tiene lugar en el árbol;
    Actions -> Estados alcanzables desde algún estado cualquiera;
    Root -> Nodo top u origen del árbol;
    Origin -> Estado origen de algún estado cualquiera;
    Final -> Estado sin acciones posibles;
    Level -> Nivel del estado por defecto root = 0;
    Tree -> Estructura que modela los estados del problema;
    Cost -> Costo para llegar a ese estado desde el inicio;
    Source -> Representación matricial de algún estado;
    State -> Estado a priori;

Concepto

Los arboles son estructuras de datos complejas que nos permiten modelar el mundo, siguiendo ciertas restricciones adaptadas de la propia naturaleza del problema.

Una simple representación de un árbol puede ser la siguiente:

Los arboles con los que trabajaremos contienen una raíz destacada la cual es el origen del estado, por lo cual solo hay un camino origen asociado a un estado viniendo desde otro.

Representación

Crear un estado

Node state = new Node(“State”,1);
Crear un Árbol de soluciones
Node A = new Node(“A”,1);
Tree tree = new Tree(A,”goal”,”name”);

Asignar estados…

Node B = new Node(“B”,1);
Node C = new Node(“C”,1);
Node D = new Node(“D”,2);

tree.flourish(A,B);
tree.flourish(A,C);
tree.flourish(A,D);

Funciones Bioinspiradas

• Flourish -> Floresca un estado en otro.
• Wither -> Elimine un estado.
• Flush -> Limpie el espacio de estados.
• Size -> Tamaño del espacio de estados.
• onList -> Representación matricial del árbol.

Funciones de Contexto

• A*
• BFS
• UCS
• DFS
• DLS
• IDS
• BS

Listas de Trabajo

•     FIFO
•     LIFO
•     SORT

Ejemplo implementando A*

Es posible modelar el problema de juguete conocido del juego puzzle 8, en el cual se busca llegar de un estado inicial a otro, en el menor número de movimientos posibles.

Análisis

La representación a priori del problema es la posición de las fichas respecto al estado final, esta información por si misma nos permite alcanzar una solución puesto que, si el orden de las fichas es igual al del estado objetivo, hemos encontrado la solución, Solo basta con representar cada estado como una matriz y tomar el espacio vacío como valor “0”.

Es preciso notar la intima relación que existe, si obtuviéramos coordenadas arbitrarias respecto a un eje en cada posición y las comparáramos, esta relación nos permite aplicar una las heurísticas más famosas de este problema, la heurística de Manhattan.


Nota: La función heurística nos permite obtener abstractamente información más consistente sobre el problema y su solución, es un tipo de regla de 3 para la estimación de un problema.

La heurística de manhattan nos da la distancia mínima entre dos coordenadas de una forma parecida a la utilizada en la distancia euclidiana, la naturaleza de obtención de esta nos permite encontrar una estimación a nuestro problema. En el juego solo es posible mover el espacio vacío “0”, en forma vertical o horizontal, la distancia de manhattan se basa precisamente en esta analogia.

Supongamos que modelamos el siguiente árbol…


El estado Inicial es A representado por {2,8,3,1,6,4,7,0,5}

El estado final es M representado por {1,2,3,8,0,4,7,6,5}

·         Numero de piezas en desorden respecto al estado M de A : 4 (2,8,1,6)
·         Heurística de manhattan del estado inicial respecto a M : 5

La función de evaluación será el valor de la heurística + coste, que en este caso lo definiremos como el nivel del estado en el árbol.

Test - Implementacion

Aplicando el algoritmo A*


    A* es óptimamente eficiente esto significa que no existe otro algoritmo que expanda menos nodos antes de encontrar la solución, esta demás decir que es completo y óptimo.

Comparado con otros algoritmos de búsqueda no Informada..

BFS

UCS

Conclusiones

Las estructuras aquí mostradas son escalables a cualquier tipo de problema en la vida real y ofrecen una buena base para generar un modelo solución, los algoritmos con los que cuenta, son usados hoy en día para resolver muchas cosas dentro de la informática, en especial A*, desde juegos de rol, hasta predicciones financieras en wall-street.

Mas allá de la IA…

Es responsabilidad del analista la correcta abstracción del entorno para una óptima implementación. Tener la capacidad de imaginar el comportamiento de los agentes de acuerdo a sus propias percepciones y el problema en si mismo, permitirá modelar objetos, que en la realidad serán artilugios matemáticos de esa intima relacion del analista y el problema, estas heurísticas serán la esencia de la solución, al final una inteligencia optima no solo es fruto de un estupendo algoritmo de búsqueda, sino también de la imaginación del desarrollador.

REPOSITORIO GITHUB && EJEMPLO

https://github.com/DanielRosillo/Cherry-Star

REFERENCIAS

Russell, S., Norving, P. 2010. Artificial Intelligence A modern Approach. Third Edition. Pearson Education.

Sara El-Sayed El-Metwally
    https://www.codeproject.com/articles/203828/ai-simple-implementation-of-uninformed-search-stra

Jose Luis Iglesias Feria
    https://descubriendolaia.blogspot.com/