Debido a que la búsqueda es el núcleo de
muchos procesos inteligentes, es adecuado estructurar los programas de IA de
forma que se facilite describir y desarrollar el proceso de búsqueda. Los
sistemas de producción proporcionan tales estructuras. Un sistema de producción
consiste en:
• Un conjunto de reglas.
• Una
o más bases de datos/conocimiento.
• Una
estrategia de control que especifique el orden en el que las reglas se comparan
con la base de datos, y la forma de resolver los conflictos que surjan cuando
varias reglas puedan ser aplicadas a la vez.
• Un
aplicador de reglas.
El proceso de solución del problema puede
modelarse como un sistema de producción. El problema que se plantea es escoger
la estructura de control apropiada para el sistema de producción con el fin de
que el proceso de búsqueda sea lo más eficiente posible.
Un problema de búsqueda en I.A. consta de:
Un espacio de estados.
Un conjunto de operadores (acciones, con
costes).
Un estado inicial (punto de partida de la
búsqueda búsqueda).
Una función objetivo (comprueba si el estado
actual corresponde a una solución del problema problema)
La búsqueda la realiza un programa (o
agente).
El espacio de búsqueda será un grafo dirigido
en el que cada nodo representa un posible estado del sistema.
NOTA:
Dependiendo del problema, cada nodo incluirá una descripción completa del
sistema, o bien sólo las modificaciones necesarias para pasar de un nodo padre
a su hijo.
Búsqueda
en un espacio de estados
Grafo del espacio de estados / Grafo implícito
Representación matemática de un problema de
búsqueda (nodos: estados; arcos: operadores): Grafo teórico que representa
todas las posibles transformaciones del sistema aplicando todos los operadores
posibles recursivamente.
Debido a su complejidad exponencial, que
requeriría una cantidad inviable de memoria y tiempo, el grafo del espacio de
estados no puede generarse por completo.
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.
Planteamiento del problema del 8-puzle
Un tablero cuadrado
(3x3) en el que hay situados 8 bloques cuadrados numerados (con lo cual se deja
un hueco del tamaño de un bloque). Un bloque adyacente al hueco puede
deslizarse hacia él. El juego consiste en transformar una posición inicial en
la posición final mediante el deslizamiento de los bloques. En particular,
consideramos el estado inicial y final siguientes:
Estado: descripción
de una posible situación en el problema
• Abstracción de propiedades
Importancia de una
buena representación de los estados
•
Sólo considerar información relevante para el problema
•
La representación escogida influye en el número de estados y éste en los
procedimientos de búsqueda de soluciones
Ejemplo: 8-puzle:
Elementos de la representación:
• relevante: localización de cada bloque y del
hueco;
•
irrelevante: tipo de material de los bloques, colores de los bloques.
Ejemplo del 8-puzle:
Representaciones del estado
•
Descripción de la posición exacta de cada uno de los bloques
•
Representación vs. implementación
•
Lista: (2 8 3 1 6 4 7 H 5), (2 8 3 4 5 H 7 1 6)
•
Matriz: ((2 8 3)(1 6 4)(7 H 5))
• Literales: ((primera-izquierda 2)
(primera-centro 8) ...)
•
Número de estados: 9! = 362.880.
Operadores
en el 8 puzle
• Mover el hueco hacia arriba
• Mover el hueco hacia abajo
• Mover el hueco hacia la derecha
• Mover el hueco hacia la izquierda
• Descripción del operador “Mover el hueco hacia arriba”
• Aplicabilidad: es aplicable a estados que no tengan el hueco en la
primera fila
• Resultado de aplicarlo: intercambiar las posiciones del hueco y del
bloque que está encima de éste
·
Los tres restantes, análogamente
Descripción
del objetivo
• Usualmente, un conjunto de estados, que
llamaremos finales
• A veces, aunque no necesariamente, un
único estado final
• Ejemplo del 8-puzle (un único estado
final)
Formas de describir
los estados finales:
•
Enumerativa.
•
Declarativa.
Definición
de solución de un problema.
•
Secuencia de acciones a realizar para conseguir el objetivo
• Secuencia de operadores cuya aplicación
desde el estado inicial obtiene un estado final
•
Ejemplo: Una solución del 8-puzle
Ruiz Reina, J. (2012, diciembre). IA. Recuperado de https://www.cs.us.es/cursos/ia1/temas/tema-02.pdf
Guerri, M. (2020, 10 febrero). ▷ Misioneros y caníbales. Recuperado de https://www.psicoactiva.com/puzzleclopedia/misioneros-y-canibales/
No hay comentarios:
Publicar un comentario