Breadth first search (primera extensión de búsqueda).
Método
Esto busca el nodo objetivo entre todos los nodos de una generación particular, antes de expandirse aún más.
Algoritmo
1. Formar una cola de un elemento de Q, que consiste en el nodo raíz
2. Hasta que Q es vacío o el objetivo se ha alcanzado BBC, determina si el primer elemento de Q es el objetivo. si lo es, no hacer nada b. si no es así, eliminar el primer elemento de Q y añadir los niños del primer elemento, si lo tiene a la parte posterior P.
3. Si el objetivo es alcanzado, el éxito, el fracaso más.
1. Formar una cola de un elemento de Q, que consiste en el nodo raíz
2. Hasta que Q es vacío o el objetivo se ha alcanzado BBC, determina si el primer elemento de Q es el objetivo. si lo es, no hacer nada b. si no es así, eliminar el primer elemento de Q y añadir los niños del primer elemento, si lo tiene a la parte posterior P.
3. Si el objetivo es alcanzado, el éxito, el fracaso más.
Evaluación
si hay más de un nodo objetivo, siempre coger el más cercano al nodo en la generación. esto es de valor si los tres si no balanceada, pero inútil si los nodos meta se encuentran en niveles similares.
Esto es una búsqueda completa.
si hay más de un nodo objetivo, siempre coger el más cercano al nodo en la generación. esto es de valor si los tres si no balanceada, pero inútil si los nodos meta se encuentran en niveles similares.
Esto es una búsqueda completa.
Costo de la búsqueda
considerar un factor de tres con ramificación b. a una profundidad d, habrá nodos b. esto provoca una explosión exponencial de tamaño del árbol.
considerar un factor de tres con ramificación b. a una profundidad d, habrá nodos b. esto provoca una explosión exponencial de tamaño del árbol.
Aprovechamiento del tiempo es de orden b. esto es muy ineficiente.
Espacio La eficiencia es también de orden b. esto es muy ineficiente.
No óptimas
este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.
este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.
No hay comentarios:
Publicar un comentario