Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Búsqueda bidireccional

No description
by

Juan Pablo Arnaudo

on 21 August 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Búsqueda bidireccional

Búsqueda bidireccional
Alumnos:
Arnaudo Juan Pablo BIS430631
Lobo Mauricio BIS430689
Neyra Fabricio BIS430642
Rivero Emilio BIS430633

La busqueda bidireccional se puede aplicar
a un problema en el que conocemos
la situación inicial (descripción) del mismo
y del que, además, conocemos una meta
de manera explícita.
En este caso podemos utilizar dos procesos de búsqueda:


desde la descripción del problema hacia la solución

desde la meta hacia la descripción del problema

Para la representación con grafos, tenemos uno para la búsqueda desde el nodo raíz al nodo meta y otro para la búsqueda desde la meta hasta el nodo raíz.

Durante el proceso se alterna entre uno y otro grafo.

Si la alternancia es de nivel en nivel dado un nivel n-1, en la búsqueda encadenada hacia delante se generan todos los estados del nivel n comprobando si alguno de ellos está en la
frontera de exploración de la otra búsqueda.

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 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.
Se puede utilizar en problemas en los que se conoce la meta y el estado inicial.

si es así, las dos búsquedas se han encontrado, y la solución será la composición del resultado de las dos búsquedas:

El camino desde la situación inicial a la meta pasando por el estado común.
La pertenencia a la frontera de exploración se puede comprobar en solo uno de los grafos o en los dos.

Para que se pueda realizar este tipo de búsqueda se tienen que cumplir dos condiciones:

• Los operadores han de ser reversibles.

• Que la meta sea explícita.

En síntesis:
Se llevan a la vez dos búsquedas.
Al menos una de estas dos búsquedas debe ser en anchura.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba.
El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.


Tenemos dos cántaros de agua, uno de 4 litros y otro de 3 litros
de capacidad.
– Además tenemos un grifo para llenar los cántaros.
– Tanto cuando se llena un cántaro como cuando se vacía la operación
supone o llenar el cántaro hasta su capacidad máxima o vaciarlo del
todo, respectivamente.
– Inicialmente tenemos ambos cántaros vacíos
– Se desea llegar a la siguiente situación: que el cántaro de 4 litros de
capacidad quede lleno por la mitad y el cántaro de 3 litros quede
vacío.
• Formular este problema como un problema de búsqueda: definir
la representación de estados, cuál es el estado inicial, los
operadores y el/los estados objetivos.
• Aplicar búsqueda bidireccional en anchura para mostrar el
camino solución del problema. Se supone que todos los
operadores tienen el mismo coste. Si se genera un estado
repetido indicarlo y no seguir expandiendo por él. Si en algún
momento no se puede aplicar ningún operador a un determinado
estado indicar dicho suceso en el árbol.
Full transcript