EVITAR ESTADOS REPETITIVOS

INTRODUCCIÓN

Los arboles de la búsqueda para evitar estados repetidos indican que estos problemas son infinitos, pero si ponemos parte de los estados repetidos, podemos cortar el árbol de búsqueda en un tamaño finito, generando solo la parte del árbol que atraviesa el grafo del espacio de estados. 

EVITANDO ESTADOS REPETIDOS

Se ha ignorado la posibilidad de expandir nodos que ya visitamos en algún camino. En muchos problemas, no podemos evitar el tener estados repetidos, en particular, todos los problemas con operadores reversibles.

Los árboles de búsqueda en este caso pueden ser infinitos, pero si eliminamos los repetidos los podemos volver finitos.

Opciones:

• No regresar al estado anterior.
• No crear caminos con ciclos
• No generar algún estado que fue generado antes. Esto requiere guardar en memoria todos los estados generados.

Los algoritmos de búsqueda normalmente usan una tabla hash, y el qué tanto guardamos depende muchas veces del problema. Entre más ciclos tenga es más probable que el evitar generar estados ya generados sirva más.

Hasta este punto, casi hemos ignorado una de las complicaciones más importantes al proceso de búsqueda: la posibilidad de perder tiempo expandiendo estados que ya han sido visitados y expandidos. Para algunos problemas, esta posibilidad nunca aparece; el espacio de estados es un árbol y hay solo un camino a cada estado. La formulación eficiente del problema de las ocho reinas (donde cada nueva reina se coloca en la columna vacía de más a la izquierda) es eficiente en gran parte a causa de esto (cada estado se puede alcanzar solo por un camino). Si formulamos el problema de las ocho reinas para poder colocar una reina en cualquier columna, entonces cada estado con n reinas se puede alcanzar por n\ caminos diferentes.

Para algunos problemas, la repetición de estados es inevitable. Esto incluye todos los problemas donde las acciones son reversibles, como son los problemas de búsqueda de rutas y los puzles que deslizan sus piezas. Los arboles de la búsqueda para estos problemas son infinitos, pero si podamos parte de los estados repetidos, podemos cortar el árbol de búsqueda en un tamaño finito, generando solo la parte del árbol que atraviesa el grafo del espacio de estados. Considerando solamente el árbol de búsqueda hasta una profundidad fija, es fácil encontrar casos donde la eliminación de estados repetidos produce una reducción exponencial del coste de la búsqueda. En el caso extremo, un espacio de estados de tamaño d + 1.

Se convierte en un árbol con 2rf hojas.

Un ejemplo más realista es la rg 31a rectangular como se ilustra

Sobre una rejilla, cada estado tiene cuatro sucesores, entonces el árbol de búsqueda, incluyendo estados repetidos, tiene 4rf hojas; pero hay solo 2a* estados distintos en c/pasos desde cualquier estado. Para d = 20, significa aproximadamente un billón de nodos, pero aproximadamente 800 estados distintos.

Entonces, si el algoritmo no detecta los estados repetidos, estos pueden provocar que un problema resoluble llegue a ser irresoluble. La detección por lo general significa la comparación del nodo a expandir con aquellos que han sido ya expandidos; si se encuentra un emparejamiento, entonces el algoritmo ha descubierto dos caminos al mismo estado y puede desechar uno de ellos.

Para la búsqueda primero en profundidad, los únicos nodos en memoria son aquellos del camino desde la raíz hasta el nodo actual. La comparación de estos nodos permite al algoritmo descubrir los caminos que forman ciclos y que pueden eliminarse inmediatamente.

CONCLUSIONES

Uno de los problemas en encontrar una solución válida, es que en el algoritmo repite los mismos estados que se podían eliminar; así que el algoritmo pierde el tiempo y se vuelve más tedioso llegar a la mencionada solución.

Entre los errores sin sensores, de contingencia y de exploración se debería tomar medidas para evitar que no sucedan y que nuestro agente se desenvuelva de la mejor manera.

BIBLIOGRAFÍA

Russell S. y P. Norvig, Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 51-62.

Díaz, F.2008.Resolucion de problemas mediante Búsqueda.(En línea).EC.Consultado , 30 de Mayo del 2015