12-18-2006, 03:34 AM
Les dejo aquí una pequeña demostración que tuve que hacer para IA en la facu hace un tiempo atrás, espero que les sirva...
Objetivo: Implementar algoritmos planificadores de búsqueda que permitan la resolución de un Puzzle de 9 fichas.
Métodos Utilizados: los métodos utilizados son dos, el primero, denominado ?Primero el Mejor? el cual combina las ventajas de los algoritmos primero en profundidad y primero en anchura. Sigue un camino a la vez, pero puede cambiarse a otro camino que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
Abiertos - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
Cerrados - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
Función Heurística - Permite que el algoritmo busque primero por caminos que son o parecen más prometedores.
El segundo método utilizado es el algoritmo ?A*?, que es similar al método anterior pero con la única diferencia que éste garantiza que encontrará un sendero óptimo a un objetivo, en caso de que exista solución, esto es debido a una evaluación más eficiente de los costos, por consiguiente se puede afirmar que éste método es más eficiente que el anterior.
En este caso la función heurística de evaluación está conformada por f(n) = g(n) + h(n), donde h(n) representa el valor heurístico del nodo a evaluar, y g(n), el coste real del camino recorrido para llegar a dicho nodo. A* mantiene dos estructuras de datos auxiliares mencionadas en el método anterior (ABIERTOS-CERRADOS).
Características del sistema: el sistema implementado se desarrolló con el lenguaje de programación ?JAVA?, se utilizan 2 listas, se generan matrices multidimensionales para la comparación y evaluación de costos/movimientos.
El sistema esta conformado por los siguientes archivos:
Puzzle9.tar.gz <- Contiene los archivos que se describen a continuación.
Puzzle.java <- lanzador del aplicativo.
Nodo.java <- clase para la generación de nodos en las listas.
Lista.java <- clase para la generación de listas.
Leer.java <- clase para capturar caracteres ingresados por teclado.
Util.java <- clase con varios métodos para la comparación y evaluación de opciones/nodos durante el recorrer de los caminos para llegar a la solución óptima.
Particularidades del desarrollo e implementación: Por cuestión de tiempo el sistema se implemento para la utilización en modo texto bajo una consola de comandos.
Además por el mismo problema, no se pudo llegar a implementar más cantidad de métodos de búsqueda de solución óptima.
Resultados: se pudo comprobar la efectividad del método Primero el Mejor y A*, cabe aclarar que en algunos casos se llegó a un bucle infinito.
Limitaciones comprobadas: no siempre se llega a una solución óptima. También se puede caer en un bucle infinito, se necesitan muchas iteraciones para dar con la solución objetivo.
Conclusiones: si bien se generaron algunos resultados negativos, se pudo comprobar la efectividad del método Primero el Mejor y el del algoritmo A*. Buscando por Internet pude encontrar implementaciones de algoritmos con mejor efectividad o alteraciones a los anteriores que los hacen más efectivos, pero la conclusión que puedo proveer es que me sirvió como punta pié para conocer el funcionamiento y desarrollo de los mismos.
Adjunto los fuentes...
Cualquier duda o comentario bienvenidos sean... se puede mejorar... y/o agregar más métodos...
Salu2...
Objetivo: Implementar algoritmos planificadores de búsqueda que permitan la resolución de un Puzzle de 9 fichas.
Métodos Utilizados: los métodos utilizados son dos, el primero, denominado ?Primero el Mejor? el cual combina las ventajas de los algoritmos primero en profundidad y primero en anchura. Sigue un camino a la vez, pero puede cambiarse a otro camino que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
Abiertos - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
Cerrados - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
Función Heurística - Permite que el algoritmo busque primero por caminos que son o parecen más prometedores.
El segundo método utilizado es el algoritmo ?A*?, que es similar al método anterior pero con la única diferencia que éste garantiza que encontrará un sendero óptimo a un objetivo, en caso de que exista solución, esto es debido a una evaluación más eficiente de los costos, por consiguiente se puede afirmar que éste método es más eficiente que el anterior.
En este caso la función heurística de evaluación está conformada por f(n) = g(n) + h(n), donde h(n) representa el valor heurístico del nodo a evaluar, y g(n), el coste real del camino recorrido para llegar a dicho nodo. A* mantiene dos estructuras de datos auxiliares mencionadas en el método anterior (ABIERTOS-CERRADOS).
Características del sistema: el sistema implementado se desarrolló con el lenguaje de programación ?JAVA?, se utilizan 2 listas, se generan matrices multidimensionales para la comparación y evaluación de costos/movimientos.
El sistema esta conformado por los siguientes archivos:
Puzzle9.tar.gz <- Contiene los archivos que se describen a continuación.
Puzzle.java <- lanzador del aplicativo.
Nodo.java <- clase para la generación de nodos en las listas.
Lista.java <- clase para la generación de listas.
Leer.java <- clase para capturar caracteres ingresados por teclado.
Util.java <- clase con varios métodos para la comparación y evaluación de opciones/nodos durante el recorrer de los caminos para llegar a la solución óptima.
Particularidades del desarrollo e implementación: Por cuestión de tiempo el sistema se implemento para la utilización en modo texto bajo una consola de comandos.
Además por el mismo problema, no se pudo llegar a implementar más cantidad de métodos de búsqueda de solución óptima.
Resultados: se pudo comprobar la efectividad del método Primero el Mejor y A*, cabe aclarar que en algunos casos se llegó a un bucle infinito.
Limitaciones comprobadas: no siempre se llega a una solución óptima. También se puede caer en un bucle infinito, se necesitan muchas iteraciones para dar con la solución objetivo.
Conclusiones: si bien se generaron algunos resultados negativos, se pudo comprobar la efectividad del método Primero el Mejor y el del algoritmo A*. Buscando por Internet pude encontrar implementaciones de algoritmos con mejor efectividad o alteraciones a los anteriores que los hacen más efectivos, pero la conclusión que puedo proveer es que me sirvió como punta pié para conocer el funcionamiento y desarrollo de los mismos.
Adjunto los fuentes...
Cualquier duda o comentario bienvenidos sean... se puede mejorar... y/o agregar más métodos...
Salu2...