Hispanopedia Wiki
Articulo de referencia

Espacio de estados (informática)

Vacuum World, un problema de camino más corto con un espacio de estados finito. En ciencias de la computación , un espacio de estados es un espacio discreto que representa el co...

Hispanopedia WikiContenido en espanolLectura gratuita
Vacuum World, un problema de camino más corto con un espacio de estados finito.

En ciencias de la computación , un espacio de estados es un espacio discreto que representa el conjunto de todas las configuraciones posibles de un sistema. [ 1 ] Es una abstracción útil para razonar sobre el comportamiento de un sistema dado y se utiliza ampliamente en los campos de la inteligencia artificial y la teoría de juegos .

Por ejemplo, el problema de juguete Vacuum World tiene un espacio de estados discreto y finito en el que existe un conjunto limitado de configuraciones en las que pueden encontrarse el vacío y la suciedad. Un sistema de "contador", donde los estados son los números naturales que comienzan en 1 y se incrementan con el tiempo [ 2 ] , tiene un espacio de estados discreto infinito. La posición angular de un péndulo sin amortiguación [ 3 ] es un espacio de estados continuo (y, por lo tanto, infinito).

Definición

Los espacios de estados son útiles en informática como un modelo simple de máquinas. Formalmente, un espacio de estados se puede definir como una tupla [ N , A , S , G ] donde:   

  • N es un conjunto de estados
  • A es un conjunto de arcos que conectan los estados.
  • S es un subconjunto no vacío de N que contiene estados iniciales.
  • G es un subconjunto no vacío de N que contiene los estados objetivo.

Propiedades

Un estado válido en el espacio de estados del rompecabezas de las ocho reinas.

Un espacio de estados tiene algunas propiedades comunes:

Por ejemplo, el Mundo de la Aspiradora tiene un factor de ramificación de 4, ya que la aspiradora puede terminar en 1 de 4 casillas adyacentes después de moverse (suponiendo que no puede permanecer en la misma casilla ni moverse en diagonal). Los arcos del Mundo de la Aspiradora son bidireccionales, puesto que se puede llegar a cualquier casilla desde cualquier casilla adyacente, y el espacio de estados no es un árbol, ya que es posible entrar en un bucle moviéndose entre 4 casillas adyacentes cualesquiera.

Los espacios de estados pueden ser infinitos o finitos, y discretos o continuos.

Tamaño

El tamaño del espacio de estados para un sistema dado es el número de configuraciones posibles del espacio. [ 3 ]

Finito

Si el tamaño del espacio de estados es finito, calcular el tamaño del espacio de estados es un problema combinatorio . [ 4 ] Por ejemplo, en el rompecabezas de las ocho reinas , el espacio de estados se puede calcular contando todas las formas posibles de colocar 8 piezas en un tablero de ajedrez de 8x8. Esto es lo mismo que elegir 8 posiciones sin reemplazo de un conjunto de 64, o

(648)=4,426,165,368{\displaystyle {\binom {64}{8}}=4.426.165.368}

Esto es significativamente mayor que el número de configuraciones legales de las reinas, 92. En muchos juegos, el espacio de estados efectivo es pequeño en comparación con todos los estados alcanzables/legales. Esta propiedad también se observa en el ajedrez , donde el espacio de estados efectivo es el conjunto de posiciones que se pueden alcanzar mediante movimientos legales. Esto es mucho menor que el conjunto de posiciones que se pueden lograr colocando combinaciones de las piezas de ajedrez disponibles directamente en el tablero.

Infinito

Todos los espacios de estados continuos pueden describirse mediante una función continua correspondiente y, por lo tanto, son infinitos. [ 3 ] Los espacios de estados discretos también pueden tener un tamaño ( contablemente ) infinito, como el espacio de estados del sistema de "contador" dependiente del tiempo, [ 2 ] similar al sistema en la teoría de colas que define el número de clientes en una fila, que tendría un espacio de estados {0, 1, 2, 3, ...}.

Exploración

Explorar un espacio de estados es el proceso de enumerar los estados posibles en busca de un estado objetivo. El espacio de estados de Pac-Man , por ejemplo, contiene un estado objetivo cuando se han comido todas las bolitas de comida, y se explora moviendo a Pac-Man por el tablero. [ 5 ]

Buscar estados

Un estado de búsqueda es una representación comprimida de un estado del mundo en un espacio de estados y se utiliza para la exploración. Los estados de búsqueda se utilizan porque un espacio de estados a menudo codifica más información de la necesaria para explorarlo. Comprimir cada estado del mundo a solo la información necesaria para la exploración mejora la eficiencia al reducir el número de estados en la búsqueda. [ 5 ] Por ejemplo, un estado en el espacio de Pac-Man incluye información sobre la dirección en la que Pac-Man está mirando (arriba, abajo, izquierda o derecha). Dado que cambiar de dirección en Pac-Man no tiene ningún costo, los estados de búsqueda para Pac-Man no incluirían esta información y reducirían el tamaño del espacio de búsqueda en un factor de 4, uno por cada dirección en la que Pac-Man podría estar mirando.

Métodos

Los algoritmos de búsqueda estándar son eficaces para explorar espacios de estados discretos. Los siguientes algoritmos demuestran completitud y optimalidad en la búsqueda de un espacio de estados: [ 5 ] [ 6 ]

Estos métodos no se extienden de forma natural a la exploración de espacios de estados continuos. Explorar un espacio de estados continuo en busca de un estado objetivo dado equivale a optimizar una función continua arbitraria , lo cual no siempre es posible; véase optimización matemática .

Véase también

  • Aventuras en el espacio estatal : Un vídeo que visualiza el espacio estatal de Klotski.

Referencias

  1. ↑ Nykamp, ​​Duane. "Definición de espacio de estados" . Math Insights . Consultado el 17 de noviembre de 2019 .
  2. 1 2 Papernick, Norman. "Estados infinitos y transiciones de estados infinitos" . Universidad Carnegie Mellon . Recuperado el 12 de noviembre de 2019 .
  3. 1 2 3 Nykamp, ​​Duane. "La idea de un sistema dinámico" . Math Insights . Recuperado el 12 de noviembre de 2019 .
  4. ↑ Zhang, Weixong (1999). Búsqueda en el espacio de estados: algoritmos, complejidad, extensiones y aplicaciones . Springer. ISBN 978-0-387-98832-0.
  5. 1 2 3 Abbeel, Pieter. "Conferencia 2: Búsqueda no informada" . UC Berkeley CS188 Introducción a la IA . Recuperado el 30 de octubre de 2019 .
  6. ↑ Abbeel, Pieter. "Clase 3: Búsqueda informada" . UC Berkeley CS188 Introducción a la IA . Consultado el 12 de noviembre de 2019 .