Ex Posicion Grupo 6

UNIVERSIDAD MAYOR DE SAN SIMON

FACULTAD DE CIENCIAS Y TECNOLOGIA

CARRERA: INGENIERIA DE SISTEMAS

Integrantes:

Chuquichambi Flores Geovanna

Beltran Cruz Yhoseph Mario

Vaca Suarez Jesus Piero

Zambrana Arze Diego

Carrera: Ingeniería de Sistemas

Docente: Lic. Garcia Perez Carmen Rosa

Trabajo: Búsqueda Bidireccional

Fecha: 15 de Abril del 2013

Cochabamba – Bolivia

INTELIGENCIA ARTIFICIAL I-2013

Lic. García Perez Carmen Rosa

BUSQUEDA BIDIRECCIONAL INTRODUCCIÓN.-

Las estrategias de BÚSQUEDA SIN INFORMACIÓN se diferencian por el orden en que expanden los nodos. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir, sólo utiliza información acerca de si un estado es o no objetivo para guiar su proceso de búsqueda. En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

Definición.-

El propósito de la búsqueda Bidireccional es encontrar su objetivo en el menor tiempo

posible y esto se logra haciendo dos búsquedas simultáneas de ahí que el nombre de

bidireccional.

En la búsqueda bidireccional se llevan a la vez dos búsquedas: una descendente desde el

nodo Inicial y otra ascendente desde el nodo Meta. Al menos una de estas búsquedas

debe ser por anchura para que el recorrido ascendente y descendente puedan

encontrarse en algún momento (Si ambos recorridos fueran por profundidad puede ser

que ninguno se pueda encontrar en ningún momento, con lo cual no tendría sentido

realizar la búsqueda).

Se tiene que definir un tipo de búsqueda para cada mitad.

Se pueden usar las siguientes combinaciones válidas para la búsqueda bidireccional:

-descendente (búsqueda por anchura) y ascendente (búsqueda por anchura)

-descendente (búsqueda por anchura) y ascendente (búsqueda por profundidad)

-descendente (búsqueda por profundidad) y ascendente (búsqueda por anchura)

-descendente (búsqueda por profundidad) y ascendente (búsqueda por

profundidad)

(Con la última combinación puede no tener resultados y estar en una búsqueda

que nunca podría encontrar la meta)

El camino de la solución es la suma de los caminos encontrados por ambas búsquedas

desde el nodo en común hasta el nodo Inicial y el nodo Meta.



Algoritmo.-

{búsqueda bidireccional}

abierta s0 /s

meta

Repetir

Si vacía?(abierta) entonces

devolver(negativo)

nodo primero(abierta) Si comprobar(nodo) entonces

nodo_m conectar(árboles) devolver(nodo_m)

sucesores expandir(nodo)

Para cada n sucesores hacer

n.padre nodo

ordInsertar(n,abierta,final) Fin {repetir}

• usar el algoritmo para la búsqueda en profundidad • emplear el algoritmos en paralelo, empezando por el estado inicial y final

respectivamente • comprobar(nodo): comprueba si un nodo está en la lista abierta del otro árbol • conectar(árboles): conecta los dos árboles (por los primeros nodos hoja); invierte

el camino hasta el nodo meta y devuelve el nodo meta

Análisis del Algoritmo.- Completo.- Lo es, ya que las dos estrategias con en búsquedas en amplitud. Si se conoce la meta y el problema siempre se encuentra la solución. Optimo.- Si las dos estrategias son en amplitud, el algoritmo es optimo por serlo tambien las anteriores. Complejidad Temporal.-El caso peor ocurre cuando las dos búsquedas se encuentran en la mitad del grafo, es decir a profundidad “ p/2”. Si el factor de ramificación es “n” y la solución e n y la solucion esta en la profundidad “p”, el tiempo necesario para llegar a la solución será: “2(1+n+n2+n3+……..+np/2)”, ya que es el mismo tiempo para los dos. El costo temporal esta en “O (np/2)”. No se tiene en cuenta el tiempo q tarda en comprovar la frontera de exploración pues su costo es muy pequeño a comparación con el resto. Complejidad espacial.- El caso peor también cuando se cruzan a profundidad. “p/2”. En la estrategia en amplitud también vamos a almacenar “2 (np/2)” estados. Así el costo espacial tambien esta en la “O (np/2)”.



La complejidad espacial es igual a la temporal para esta búsqueda Dificultades – Cálculo de predecesores. – Varios estados objetivo. – Determinación del tipo de búsqueda en cada dirección.

Evaluación de la Búsqueda Bidireccional.-

……………………………………….

•

Si en un problema el factor de ramificación b es el mismo en ambas direcciones, la búsqueda bidireccional puede ser muy útil. Si la solución está a profundidad d, entonces la solución estará a:

O(2bd/2) = O(bd/2) pasos.

Su interés radica en la reducción de la complejidad.



bd/2 + bd/2 << bd Conclusión del análisis del algoritmo.- 1. Cada una de las búsquedas se implementa en amplitud y los costes son siempre iguales a la unidad Si existe una solución n, necesariamente existirá un camino desde el nodo inicial s hasta el nodo final o meta, t. Alternando la dirección n de las búsquedas después de cada expansión n, el nodo coincidente será el que se encuentra necesariamente en la mitad de este camino. Puesto que cada uno de los algoritmos del primero en amplitud es completo, ambos encontrarán, irremediablemente, el nodo de coincidencia n. Por lo tanto, el algoritmo bidireccional resultante es necesariamente completo. Más aún n, puesto que cada búsqueda del primero en amplitud es admisible, ambas encontrarán el camino óptimo hasta el nodo de coincidencia n. Por supuesto, la concatenación n de los caminos con el menor coste, resultara necesariamente en un camino óptimo y, por lo tanto, el algoritmo resultante es necesariamente admisible. 2. Ambas búsquedas se implementan en amplitud y los costes son cantidades arbitrarias estrictamente positivas Como antes, el algoritmo bidireccional en cuestión n es necesariamente completo. En realidad, la completitud de el algoritmo del primero en amplitud, resulta del uso de una cola, puesto que así se garantiza que “nunca se expande un nodo a profundidad (d + 1) si antes no se han expandido todos los nodos a profundidad d”, independientemente del coste de los operadores. Como antes, la completitud de los algoritmos empleados en ambas direcciones, garantizan la completitud de la implementación n bidireccional resultante. Sin embargo, ahora no sucede que cuando se genera un nodo cualquiera, n, por primera vez, se haga con el mínimo coste como ocurriera cuando los operadores tienen costes iguales a la unidad. Por lo tanto, el algoritmo del primero en amplitud no es admisible en este caso. Si no lo es, no puede garantizarse que los caminos encontrados desde cada extremo hasta el nodo de coincidencia, n, sean óptimos y, por ello, que el camino resultante lo sea. Por lo tanto, el algoritmo bidireccional resultante no es admisible en este caso. 3. Ambas búsquedas se implementan en profundidad con costes idénticos y siempre iguales a la unidad El algoritmo del primero en profundidad no es completo. Si no es completo, se sigue inmediatamente que no es admisible, puesto que si no puede garantizarse que encuentre una solución n, ¡aún n menos que encuentre la solución n optima! Por lo tanto, si no



puede garantizarse que cada una de las búsquedas encontrara, eventualmente el nodo n, se sigue que esta implementación n bidireccional no es completa. Como antes, no siendo completa, se sigue de inmediato que tampoco es admisible 4. Una búsquedas se implementan en profundidad n iterativa hacia delante y la otra búsquedas se implementan en amplitud (en la dirección n opuesta para cada iteración del algoritmo). Como se sabe, el algoritmo de profundización “n” iterativa es también completo, de modo que eventualmente alcanzara el mismo nodo “n”. El motivo es que no puede garantizarse que ambos nodos lleguen al nodo de coincidencia en el mismo instante, de modo que ambas búsquedas se cruzarían: cada vez que el algoritmo de profundización n iterativa reinicia la búsqueda, creando una nueva pila en la que introduce únicamente el nodo inicial, el algoritmo del primero en amplitud (en la dirección “n” opuesta) expandirá unos cuantos nodos antes de que el algoritmo de profundización “n” iterativa haya dejado de regenerar nodos para empezar a generar otros nuevos. Si el nodo n fuera alguno de los nodos expandidos por el algoritmo del primero en anchura mientras el algoritmo de profundidad iterativa llegaba a una nueva área del espacio de estados, la coincidencia resultaría inadvertida para el algoritmo de profundización n iterativa, que llegaría a él, pero más tarde.

Si hay varios estados meta listados en forma explícita, se puede aplicar una función de predecesor al conjunto de estados como en el caso de la búsqueda de estado múltiple. Pero si sólo hay una descripción de los estados meta, es realmente difícil (¿qué estados son predecesores de las 8 reinas en el tablero?)

Comparación de las estrategias de búsqueda.

Variables b: factor de ramificación d: profundidad mínima de un objetivo

Método no

informado

preferido



m: profundidad máxima de un estado l: límite de profundidad

El problema de los estados repetidos.-

Como se evita expandir estados que ya se expandieron en otra ruta?

* En algunos problemas se llega a un estado de una sola forma, y por ende es imposible repetir.

* Cuando los operadores son reversibles, entonces pueden obtenerse árboles infinitos (misioneros y caníbales, rutas).

Evitar las repeticiones disminuye sensiblemente el costo de la búsqueda:

1. Los árboles infinitos pueden volverse finitos.

2. En árboles finitos la reducción es muy importante.

Formas de evitar los estados repetidos:

1. No regresar al estado del que acaba de llegar. Sucesor (n) distinto a Padre (n).

2. No generar rutas que tengan ciclos. Sucesor(n) distinto a Ancestro(n).

3. No generar ningún estado que se haya generado alguna vez.

Costo

Eficiencia

Hay un compromiso entre el costo de almacenar y verificar y el costo de la búsqueda adicional a realizar.

-

+

Hay un compromiso entre el costo de almacenar y verificar y el costo de la búsqueda adicional a realizar.



• Estados: – posición de cada una de las piezas

• Acciones: – mover pieza adyacente a la

posición del “hueco”

– de 2 a 4 operadores aplicables,

según el estado

• Coste: – La aplicación de cada operador

vale una unidad

Problema: Instanciación:

• Solución: – secuencia de acciones que lleva de

un estado inicial al estado meta

Ejemplo: 8-Puzzle



Árboles de búsqueda bidireccional (evitando ciclos simples)



Árboles de búsqueda bidireccional (evitando ciclos simples)



Ventajas.-

• completo: o siempre se encuentra un nodo meta si existe

• óptimo (para operadores de coste uno): o siempre se encuentra el nodo meta menos profundo

• reduce la complejidad (en espacio y en tiempo) de forma considerable

Complejidad temporal de , siendo: b1: factor de ramificación de la búsqueda en dirección 1. b2: factor de ramificación de la búsqueda en dirección 2.

d: profundidad de la solución.

Desventajas.-

Dar el valor a ld y no disponer de algún criterio adicional para poder ordenar la selección de nodos meta a lo largo del proceso.

Su principal problema es que requiere mucho espacio. Es pocas veces aplicable.

El factor de ramificación de la búsqueda inversa podría ser mucho mayor que el de

la directa.

Complejidad espacial de , siendo: bi: factor de ramificación de la búsqueda de la que se guarda el árbol en memoria.

Puede ser muy difícil o imposible encontrar una función inversa. Varios estados meta

Factor de ramificación del árbol inverso puede ser mayor

Ejemplo: 8 reinas: estado meta colocar 8 reinas en el tablero

Conclusión.-

Si una de las dos estrategias es en amplitud, el algoritmo es completo. La ventaja de esta búsqueda es que reduce a la mitad el factor exponencial del coste computacional con respecto a la búsqueda en amplitud siendo a su vez, la principal desventaja desde el punto



de vista del costo de almacenamiento (Aunque se reduce drásticamente el número de nodos a almacenar este es todavía muy grande).

Se puede utilizar en problemas en que se conoce la meta y el estado inicial. Si es aplicable reduce la complejidad. Finalmente la búsqueda bidireccional posee la ventaja de reducir a la mitad el factor exponencial del costo computacional con respecto a la búsqueda en amplitud, siendo a su vez, la principal desventaja desde el punto de vista del costo de almacenamiento (aunque se reduce drásticamente el número de nodos a almacenar, este es todavía muy grande).

Bibliografía.- Inteligencia Artificial. Un enfoque moderno – Norvig & Russell – Prentice Hall

1995. (cap 3)

Inteligencia Artificial - Elaine Rich – Kevin Knight – 2ª edición - Mc Graw Hill

1994. (cap 2)

AIMA. Capítulo 3, primera edición.

AIMA. Chapter 3, second edition.

INTELIGENCIA ARTIFICIAL: INTRODUCCIÓN Y TAREAS DE BÚSQUEDA.

VERSIÓN 20100619 - Roberto J. de la Fuente López

INTELIGENCIA ARTIFICIAL Teoría y proyectos. tercera edición - M. C Ricardo

Fuentes Covarrubias.

Stuart J. Russell y Peter Norvig – INTELIGENCIA ARTIFICIAL UN ENFOQUE

MODERNO segunda edición

Distintos trabajos prácticos realizados por otras universidades.

www.dsi.fceia.unr.edu.ar/downloads/IIA/.../busqueda2007.ppt

http://unixlandia.com/web_interna/attachments/509_IntroSistemasBusqueda.pdf

www.wiphala.net/.../class_a2_uninformed_search_strategies.ppt - Perú

www.innova.uned.es/webpages/.../iartificial/.../ia_intro_busqueda.pdf

Documents

Ex Posicion Grupo 6