La resolución de problemas es una capacidad que consideramos inteligente. Somos capaces de resolver problemas muy diferentes.
Un problema típico de la Inteligencia Artificial
consiste en buscar un estado concreto entre un conjunto
determinado, al que se le llama espacio de estados.
El objetivo es que un programa también sea capaz de resolverlos.
El objetivo es que un programa también sea capaz de resolverlos.
Resolución de Problemas
Deseamos definir
cualquier tipo de problema de manera que se pueda
resolver
automáticamente
Necesitamos:
ü Una
representación común para todos los problemas
ü Algoritmos
que usen alguna estrategia para resolver problemas definidos en esa representación
común
ü
Definición de un
Problema
.jpg)
Si abstraemos los
elementos de un problema podemos identificar:
ü Un
punto de partida
ü Un
objetivo a alcanzar
ü Acciones
a nuestra disposición para resolver el problema
ü Restricciones
sobre el objetivo
ü Elementos
que son relevantes en el problema definidos por el tipo de
ü dominio
ü
Existen diferentes
formas de representar problemas para resolverlos de manera automática
ü Representaciones
generales
*Espacio de estados: un
problema se divide en un conjunto de pasos de resolución desde el inicio hasta
el objetivo
*Reducción a
subproblemas: un problema se puede descomponer en una jerarquía de subproblemas
ü Representaciones
para problemas específicos
*Resolución de juegos
*Satisfacción de
restricciones
Representación de
problemas: Estados
*Podemos
definir un problema por los elementos que intervienen y sus relaciones
*En cada instante de la
resolución de un problema esos elementos tendrán unas características y
relaciones específicas
*Denominaremos Estado a
la representación de los elementos que describen el problema en un momento
*Distinguiremos dos
estado especiales el Estado Inicial (punto de partida) y el Estado Final
(objetivo del problema)
*¿Que incluir en el
estado?
Modificación del estado:
operadores
Para poder movernos
entre los diferentes estados necesitamos operadores de transformación
*Operador: Función de
transformación sobre la representación de un estado que lo convierte en otro
estado
Los operadores definen
una relación de accesibilidad entre estados
Representación de un
operador:
ü Condiciones
de aplicabilidad
ü Función
de transformación
*¿Que operadores?
¿Cuantos? ¿Que granularidad?
ESPACIO DE ESTADOS
Los estados y su
relación de accesibilidad conforman lo que se denomina espacio de estados
Representa todos los
caminos que hay entre todos los estados posibles de un problema
Podría asimilarse con
un mapa de carreteras de un problema
La solución de nuestro
problema esta dentro de ese mapa
SOLUCIÓN DE UN PROBLEMA
EN ESPACIO DE ESTADOS
ü Solución:
Secuencia de pasos que llevan del estado inicial al final (secuencia de
operadores) o también el estado final
ü Tipos
de solución: una cualquiera, la mejor, todas.
ü Coste
de una solución: Gasto en recursos de la aplicación de los operadores a los
estados. Puede ser importante o no según el problema y que tipo de solución
busquemos
DESCRIPCIÓN DE UN
PROBLEMA EN ESPACIO DE ESTADOS
ü Definir el conjunto de estados del problema (explícita o implícitamente)
ü Especificar
el estado inicial
ü Especificar
el estado final o las condiciones que cumple
ü Especificar
los operadores de cambio de estado (condiciones de aplicabilidad y función de
transformación)
ü Especificar
el tipo de solución:
*La secuencia de
operadores o el estado final
*Una solución
cualquiera, la mejor (definición de coste), . . .
BÚSQUEDA EN UN ESPACIO
DE ESTADOS
Árbol de búsqueda /
Grafo explícito
CONCLUSIÓN
Este escrito es una
breve recompilacion de algunos conceptos básicos que yo considero se deben conocer acerca de los problemas de espacio de estados en la inteligencia
artificial.
Dejo este link que encontré en la red, de ahí tome algunas percepciones que he publicado y en mi opinion
viene bien explicado todo acerca del tema. Vienen otros conceptos como:
ü Búsqueda
en el espacio de estados
ü Estructura
del espacio de estados
ü Algoritmo
Básico
ü Características
de los algoritmos
ü Algoritmo
General de Búsqueda
ü Tipos
de algoritmos
ü Búsqueda
en Anchura Prioritaria
ü Búsqueda
en Profundidad Prioritaria
ü ID
(iterative deepening): profundidad iterativa
ü ID
(iterative deepening)
ü Búsqueda
en profundidad iterativa
ü Profundidad
Iterativa
Saludos!
No hay comentarios:
Publicar un comentario