tipos de problemas que se resuelven con las técnicas de búsqueda

 

Solución de problemas con búsqueda.

 

La solución de problemas es fundamental para la mayoría de las aplicaciones de IA; existen principalmente dos clases de problemas que se pueden resolver mediante procesos computables: aquéllos en los que se utiliza un algoritmo determinista que garantiza la solución al problema y las tareas complejas que se resuelven con la búsqueda de una solución; de ésta última clase de problemas se ocupa la IA.

 

La solución de problemas requiere dos consideraciones:

·                    Representación del problema en un espacio organizado.

·                    La capacidad de probar la existencia del estado objetivo en dicho espacio.

Las anteriores premisas se traducen en: la determinación del estado objetivo y la determinación del camino óptimo guiado por este objetivo a través de una o más transiciones dado un estado inicial

 

El espacio de búsqueda, se le conoce como una colección de estados.
En general los espacios de búsqueda en los problemas de IA no son completamente conocidos de forma a priori. De lo anterior ‘resolver un problema de IA’ cuenta con dos fases:

 

·                    La generación del espacio de estados

·                    La búsqueda del estado deseado en ese espacio.

 

Debido a que ‘todo el espacio de búsqueda’ de un problema es muy grande, puede causar un bloqueo de memoria, dejando muy poco espacio para el proceso de búsqueda. Para solucionar esto, se expande el espacio paso a paso, hasta encontrar el estado objetivo.

Espacios de estados.

Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entonces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según el modelo del universo.

 

 

 

 

 

 

La respuesta es la secuencia de transformaciones cuya aplicación sucesiva lleva a la configuración deseada.

 

Los ejemplos más característicos de esta categoría de problemas son los juegos (son universos restringidos fáciles de modelar). En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuración es un estado que puede ser esquematizado gráficamente y representado en forma simbólica. Las transformaciones permitidas corresponden a las reglas o movidas del juego, formalizadas como transiciones de estado.

Entonces, para plantear formalmente un problema, se requiere precisar una representación simbólica de los estados y definir reglas del tipo condición   acción para cada una de las transiciones válidas dentro del universo modelado. La acción de una regla indica como modificar el estado actual para generar un nuevo estado. La condición impone restricciones sobre la aplicabilidad de la regla según el estado actual, el estado generado o la historia completa del proceso de solución.

El espacio de estados de un juego es un grafo cuyos nodos representan las configuraciones alcanzables (los estados válidos) y cuyos arcos explicitan las movidas posibles (las transiciones de estado). En principio, se puede construir cualquier espacio de estados partiendo del estado inicial, aplicando cada una de las reglas para generar los sucesores inmediatos, y así sucesivamente con cada uno de los nuevos estados generados (en la práctica, los espacios de estados suelen ser demasiado grandes para explicitarlos por completo).

Cuando un problema se puede representar mediante un espacio de estados, la solución computacional corresponde a encontrar un camino desde el estado inicial a un estado objetivo.

 

·         Determinísticos.

El espacio de estados determinísticos contiene un único estado inicial y seguir la secuencia de estados para la solución. Los espacios de estados determinísticos son usados por los sistemas expertos.

·         Se puede describir a su vez, que un sistema es determinístico si, para un estado dado, al menos aplica una regla a él y de solo una manera.


No determinísticos.

El no determinístico contiene un amplio número de estados iniciales y sigue la secuencia de estados perteneciente al estado inicial del espacio. Son usados por sistemas de lógica difusa.

 

 

 

 

 

En otras palabras, si más de una regla aplica a cualquier estado particular del sistema, o si una regla aplica a un estado particular del sistema en más de una manera, entonces el sistema es no determinístico.

 

 

 

ejemplo

 

descripción del juego

 

En IA, los puzzles son considerados retos para medir el desempeño de distintos algoritmos desarrollados y de comprobar los avances en juegos utilizando la información o características elegidas por el programador (número de piezas colocadas correctamente, distancia de cada nodo a su posición final, etc.).

 

OBJETIVO del juego

 

En esta práctica, el alumno elegirá un algoritmo para resolver el puzzle de N^2 – 1 para N = 4, de donde también tendrá la libertad de elegir las características o features que considere necesarias para alcanzar la solución del juego.

 

 

-DESARROLLO DE LA PRÁCTICA

1.- Identifique las reglas del Puzzle:

Observe la siguiente matriz de 4 x 4:

 

Observe que existen 15 números distintos naturales en el rango del [1, 15] y un espacio vacío, distribuidos de

forma aleatoria en la matriz. Solamente es válido permutar una posición del espacio en blanco con cualquiera

de los 4 vecinos del espacio en blanco. Por ejemplo, son movimientos válidos:

ó

 

 

 

 

 

 

 

 NO es un movimiento válido moverse en diagonales

El objetivo del Puzzle es el de ordenar la matriz, de la siguiente manera:

2.- Cree las clases o estructuras que considere necesarias.

Implemente clases o estructuras que le permitan abstraer el problema en algo más simple. No existen restricciones en este aspecto.

 

3.- Si va a utilizar la recursión, tenga cuidado.

La memoria asignada a la pila para las llamadas a recursión es muy limitada, por lo que si decide utilizar la recursión normalmente puede alcanzar una excepción en el programa causada por el desborde de dicha pila, por lo que tómese su tiempo de pensar bien en una solución iterativa, o bien, cree su propia pila de recursión y utilícela.

 

4.- Comience con los números colocados aleatoriamente en la matriz.

Considere que no todas las matrices colocadas de forma aleatoria tienen solución. Es aconsejable investigar qué posiciones iniciales de los números tienen solución.

 

5.- Pruebe el desempeño de su algoritmo.

Realice cinco pruebas en donde mida el tiempo que le toma a su algoritmo alcanzar el resultado. Promédielo y repórtelo en una tabla junto con la matriz inicial escogida. Pruebe con cuatro distintas matrices iniciales.

 

6.- Consejos.

• Implementar una estructura que recuerde si un determinado estado ya fue visitado anteriormente, para

evitar ciclos infinitos en el programa.

• Un algoritmo interesante es aquél que mide la distancia entre la posición de un nodo entre su posición

actual y la posición final a que debe llegar.

 

 

 

 

 

 

 

 

EVALUACIÓN Y RESULTADOS

 

La evaluación de esta práctica será mediante la exposición del algoritmo funcionando en clase, y un reporte escrito por los alumnos pertenecientes al curso, el cual deberá incluir imágenes o capturas de pantalla de las implementaciones realizadas, así como de las evaluaciones del desempeño de sus algoritmos. Sólo será calificación aprobatoria si el algoritmo cumple con el objetivo.

 

 

bibliografía

 

https://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r148971.PDF

 

http://inteligenciaartificial-isc.blogspot.com/p/unidad-2.html