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
