Búsqueda en el espacio de estados

Clase de algoritmos de búsqueda

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 a menudo se modelan como un espacio de estados , un conjunto de estados en los que puede encontrarse un problema. El conjunto de estados forma un gráfico donde dos estados están conectados si hay una operación que se puede realizar para 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 de la informática porque el espacio de estados es implícito : el gráfico típico del espacio de estados es demasiado grande para generarlo y almacenarlo en la memoria . En cambio, los nodos se generan a medida que se exploran y, por lo general, se descartan después. Una solución para una instancia de búsqueda combinatoria puede consistir en el estado objetivo en sí mismo o en una ruta desde un estado inicial hasta el estado objetivo.

Representación

En la búsqueda de espacio de estados, un espacio de estados se representa formalmente como una tupla , en la que: ${\displaystyle S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle }$

• ${\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 todo el espacio de estados;
• ${\displaystyle Action(s)}$es la función que establece qué acción es posible realizar en un determinado estado;
• ${\displaystyle Result(s,a)}$es la función que devuelve el estado alcanzado al realizar la acción en el estado ${\displaystyle a}$ ${\displaystyle s}$
• ${\displaystyle Cost(s,a)}$es el costo de realizar una acción en el estado . En muchos espacios de estados a es una constante, pero esto no siempre es cierto. ${\displaystyle a}$ ${\displaystyle s}$

Ejemplos de algoritmos de búsqueda en el espacio de estados

Búsqueda desinformada

Según Poole y Mackworth, los siguientes son métodos de búsqueda de espacio de estados no informados , lo que significa que no tienen ninguna información previa sobre la ubicación del objetivo. ^[1]

• Búsqueda tradicional en profundidad
• Búsqueda en amplitud
• Profundización iterativa
• Búsqueda de costo más bajo primero / Búsqueda de costo uniforme (UCS)

Búsqueda informada

Estos métodos toman la ubicación del objetivo en forma de una función heurística . ^[2] Poole y Mackworth citan los siguientes ejemplos como algoritmos de búsqueda informados:

• Búsqueda en profundidad informada/heurística
• Búsqueda codiciosa de lo mejor primero
• Búsqueda A*

Véase también

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

Referencias

1. Poole, David; Mackworth, Alan. "3.5 Estrategias de búsqueda no informadas ‣ Capítulo 3 Búsqueda de soluciones ‣ Inteligencia artificial: Fundamentos de los agentes computacionales, 2.ª edición". artint.info . Consultado el 7 de diciembre de 2017 .
2. Poole, David; Mackworth, Alan. «3.6 Búsqueda heurística ‣ Capítulo 3 Búsqueda de soluciones ‣ Inteligencia artificial: Fundamentos de los agentes computacionales, 2.ª edición». artint.info . Consultado el 7 de diciembre de 2017 .

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