Búsqueda en el espacio de estados

 Es un proceso usado en el campo de la Informática, incluyendo la Inteligencia Artificial (AI), en el cual se consideran sucesivos estados de una instancia, con la meta de encontrar un "estado final" con las características deseadas.

Los problemas se modelan a menudoo como un espacio de estados, un conjunto de estados que un contienen el problema. El conjunto de estados forma un grafo donde dos estados están conectados si hay una operación que pueda se pueda llevar a cabo para transformar el primer estado en el segundo.

La búsqueda en el espacio de estados difiere de los métodos de búsqueda tradicionales porque el espacio de estados está implícito: El grafo del espacio de estados típico es mucho es demasiado grande para generarlo y guardarlo en memoria. En su lugar, los nodos se generan en el momento en que se exploran y generalmente son descartados después. Una solución puede consistir solamente en un estado objetivo, o en un camino desde un estado inicial hasta el estado final.

Por ejemplo, en el problema de jugar al ajedrez.

• El espacio de estados son la totalidad de tableros que se puede generar en juego de ajedrez
• El estado inicial es el tablero de 8x8 donde cada celda contiene un símbolo de acuerdo a las piezas.
• El objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esta amenazado
• las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual de tablero y otra parte que describe el cambio que debe producir en el tablero.