3-1er PA
Investigar los tipos de problemas que se resuelven con las técnicas de búsqueda. Describir gráficamente problemas en términos de espacios de estado (problema de misioneros y caníbales, problemas de juego entre dos adversarios, etc).
Solución de problemas.
Existen dos tipos de
problemas que se han estado investigando en el área de Inteligencia Artificial:
Los denominados problemas de
juguete y problemas del mundo real.
Problemas de juguete
Un problema de juguete se
utiliza para ilustrar o ejercitar los métodos de resolución de problemas.
Éstos se pueden describir de
forma exacta y concisa. Esto significa que diferentes investigadores pueden
utilizarlos fácilmente para comparar el funcionamiento de los algoritmos. Un
problema del mundo real es aquel en el que la gente se preocupa por sus
soluciones. Ellos tienden a no tener una sola descripción, sin embargo se
podría dar la forma general de sus formulaciones.
El 8-puzle consiste en un
tablero de 3 x 3 con ocho fichas numeradas y un espacio en blanco. Una ficha
adyacente al espacio en blanco puede deslizarse a éste. La meta es alcanzar el
estado objetivo especificado.
La formulación de este
problema podría ser:
Ø
Espacio de
estados: La descripción de un estado especifica la localización de cada una de
las ocho fichas y el blanco en cada uno de los nueve cuadrados;
Ø Estado Inicial: cualquier estado puede ser un
estado inicial.
Ø Objetivo o estado final: Cualquier conjunto de
configuraciones puede ser el objetivo;
Ø
Reglas: Mover el
blanco a la izquierda, a la derecha, arriba o abajo.
En este juego no hemos
considerado acciones como la de sacudir el tablero cuando las piezas no se
puedan mover, o que se puedan extraer las piezas con un cuchillo y volverlas a
poner.
El 8-puzle pertenece a la
familia de puzles con piezas deslizantes, los cuales a menudo se usan como
problemas de prueba para los nuevos algoritmos de IA.
El Problema de las 8 reinas
consiste en colocar las ocho reinas en un tablero de ajedrez de manera que cada
reina no ataque a ninguna otra (Una reina ataca alguna pieza si está en la
misma fila, columna o diagonal).
Para este problema existen
dos principales formulaciones. Una formulación incremental que implica a
operadores que aumenten la descripción del estado, comenzando con un estado
vacío; esto significa que cada acción añade una reina al estado. Una
formulación completa de estados comienza con las ocho reinas en el tablero y
las mueve.
·
Espacio de
estados: La totalidad de tableros que se pueden generar con 8 reinas en el
tablero;
·
Estado Inicial:
Un tablero donde esta una reina por columna.
·
Objetivo o estado
final: Un tablero de manera que cada reina no ataque a ninguna otra;
·
Reglas: Mover una
reina a otro cuadro en la misma columna.
Problemas del mundo real
Los problemas de búsqueda de una ruta están definidos en términos de posiciones y transiciones a lo largo de ellas. Los algoritmos de búsqueda de rutas de han utilizado en una variedad de aplicaciones, tales como rutas en redes de computadores, planificación de operaciones militares, y en sistemas de planificación de viajes de líneas aéreas. Estos problemas son complejos de especificar.
Los problemas turísticos están estrechamente relacionados con los problemas de búsqueda de una ruta, pero con una importante diferencia, el espacio de estados, en este cada estado debe incluir las ciudades que ha visitado (para conocer si ha visitado ya las demás ciudades).
El problema del viajante de comercio es un problema de ruta en la que cada ciudad es visitada exactamente una vez. La tarea principal es encontrar el viaje más corto.
La navegación de un robot es
una generalización del problema de encontrar una ruta. Más que un conjunto
discreto de rutas, un robot puede moverse en un espacio continuo con un
conjunto infinito de acciones y estados posibles. Para un robot circular que se
mueve en una superficie plana, el espacio es esencialmente de dos dimensiones.
Cuando el robot tiene manos y piernas o ruedas que se deben controlar también,
el espacio de búsqueda llega a ser de muchas dimensiones.
La secuenciación para el
ensamblaje automático por un robot de objetos complejos es factibles. En los
problemas de ensamblaje, lo principal es encontrar el orden en los objetos a
ensamblar. Si se elige un orden equivocado, no habrá forma de añadir
posteriormente una parte de la secuencia sin deshacer el trabajo ya hecho.
Verificar un paso para la viabilidad de la sucesión es un problema de búsqueda
geométrico difícil muy relacionado con la navegación del robot. Así, la
generación de sucesores legales es la parte costosa de la secuenciación para el
ensamblaje.
Ejemplo con términos
de espacios de estado:
Problema del 8–puzzle:
Representación:
Estado inicial: [[2,8,3], [1,6, 4], [7, h, 5]]
Estado final: [[1,2,3], [8, h, 4], [7,6, 5]]
Operadores:
Ø Mover
el hueco a la izquierda
Ø Mover
el hueco arriba
Ø Mover
el hueco a la derecha
Ø Mover
el hueco abajo
ü Número
de estados = 9! = 362.880.
Solución:
En la imagen se muestran tres nodos, por así llamarlos, que
se encuentran en el segundo nivel de estados, que en el caso del primero y el
tercero de los nodos, en lugar de llevarnos de forma pronta del estado inicial
al estado final simplemente hacen que esto no sea posible de realizar, no como
tal que no se pueda, simplemente que lo que se busca en este caso es llegar de una
forma más rápida a la solución de lo planteado, siendo así que estos dos no
permiten ahorrarnos movimientos tomando en cuenta también que en 8-puzzle no es
posible avanzar en diagonal y el llevar el espacio vacío hasta esa posición, en
algún punto después de seleccionar nuestros operadores, volveríamos al mismo
estado inicial forzando a que sea así el segundo que realmente nos permite
pasar del estado inicial al estado final, mostrando así que el primer
movimiento es el que en este caso el más importante a realizarse.
Bibliografía
Jiménez, J. A. (Recuperado el 07/01/2021). Tema 4:
Resolución de espacios de estados. Obtenido de www.cs.us.es:
https://www.cs.us.es/~jalonso/cursos/d-pl-04/temas/tema-4.pdf
Reina, J. L.
(Recuperado el 07/01/2021). Tema 2: Representación de problemas
comoespacios de estados. Obtenido de www.cs.us.es:
https://www.cs.us.es/cursos/ia1/temas/tema-02.pdf
Comentarios
Publicar un comentario