Búsqueda en el espacio de estados

La búsqueda en el espacio de estados es un proceso utilizado en el campo de la informática , incluida la inteligencia artificial (IA), en el que se consideran configuraciones o estados sucesivos de una instancia, con la intención de encontrar un estado objetivo con la propiedad deseada.

Los problemas suelen modelarse como un espacio de estados , un conjunto de estados en los que puede encontrarse un problema. Este conjunto de estados forma un grafo donde dos estados están conectados si existe una operación que permita transformar el primer estado en el segundo.

La búsqueda en el espacio de estados suele diferir de los métodos de búsqueda tradicionales en informática porque el espacio de estados es implícito : el grafo típico de espacio de estados es demasiado grande para generarlo y almacenarlo en memoria . En cambio, los nodos se generan a medida que se exploran y, por lo general, se descartan posteriormente. Una solución a una instancia de búsqueda combinatoria puede consistir en el estado objetivo en sí mismo, o en una ruta desde algún estado inicial hasta el estado objetivo.

En la búsqueda en el espacio de estados, un espacio de estados se representa formalmente como una tupla.${\displaystyle S:\langle S,A,\operatorname {Acción} (s),\operatorname {Resultado} (s,a),\operatorname {Costo} (s,a)\rangle }$, en el cual:

• ${\displaystyle S}$es el conjunto de todos los estados posibles;
• ${\displaystyle A}$es el conjunto de acciones posibles, no relacionadas con un estado particular sino con respecto a todo el espacio de estados;
• ${\displaystyle \operatorname {Acción} (s)}$es la función que establece qué acción es posible realizar en un estado determinado;
• ${\displaystyle \operatorname {Resultado} (s,a)}$es la función que devuelve el estado alcanzado al realizar la acción${\displaystyle a}$en el estado${\displaystyle s}$;
• ${\displaystyle \operatorname {Costo} (s,a)}$es el costo de realizar una acción${\displaystyle a}$en el estado${\displaystyle s}$. En muchos espacios estatales,${\displaystyle a}$es una constante, pero esto no siempre es cierto.

• Espacio de estado
• planificación del espacio estatal
• Ramificación y acotación : método para hacer más eficiente la búsqueda en el espacio de estados podando subconjuntos del mismo.

• Stuart J. Russell y Peter Norvig (1995). Inteligencia artificial: un enfoque moderno . Prentice Hall.