Recuerda que, para incrementar tu privacidad, tambien puedes acceder al foro usando el dominio forohpysho2t5mjs.onion de la red tor.
Cherry* - IA Busqueda A* && la Heuristica de Manhattan
https://github.com/DanielRosillo/Cherry-Star
POWER BY JAVA 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-MetwallyJose Luis Iglesias FeriaFRATERNALMENTEDANIEL ROSILLO .'.