BÚSQUEDA DE METAS EN ANCHURA
Enviado por JRCR • 22 de Marzo de 2013 • 223 Palabras (1 Páginas) • 553 Visitas
BUSQUEDA SISTEMATICA.
los problemas de búsqueda, los cuales siempre tratamos en Inteligencia artificial, son no determinísticos y el orden de elementos visitados en el espacio de búsqueda depende completamente en el conjunto de datos.
Búsqueda METAS EN ANCHURA
En la búsqueda “metas en anchura" o "Breadth First" se evalúa cada nodo en un determinado nivel antes de pasar al siguiente(se visitan todos los vértices de un grafo).
PASOS.
Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo.
En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados.
Se continúa etiquetando (en el otro nivel) todos los vecinos de los hijos de v (que no hayan sido visitados aún).
En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos.
Si en alguno de los niveles se satisface el objetivo final la búsqueda se da por finalizada.
Este tipo de búsqueda no resulta ser práctica cuando para alcanzar el estado final se deben recorrer muchos niveles.
Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia en los que se encuentra la solución, sólo tras haber llegado a todos los nodos a vecinos que le antecedieron.
...