métodos de búsqueda
Métodos de
búsqueda.
Primero
en anchura (breadthfirst).
Búsqueda primero en anchura
·
Principio:
expandir el nodo menos profundo que no
haya sido expandido
·
La frontera es una
cola FIFO, i.e. nuevos sucesores van al final
Algoritmo:
1.- Crear una lista con un solo elemento
consistente en una
trayectoria o camino de longitud cero: el nodo raíz
2. Hasta que el primer camino de la lista llegue al
nodo objetivo o se llegue a la lista vacía hacer
a. Extraer el primer camino de la lista
b. Expandir el nodo final de este camino a todos
los vecinos del nodo terminal.
c. Eliminar los ciclos de los caminos expandidos.
d. Insertar estos nuevos caminos al Final de la
lista.
3. FIN Hasta
4. Si se halla el nodo meta notifique el éxito, si
no el fracaso
Si el
conjunto open se maneja como una lista FIFO, es decir, como
una cola, siempre se estará visitando primero los primeros estados en ser
generados. El recorrido del espacio de estados se hace por niveles de
profundidad.
procedure
Búsqueda_en_amplitud {
open
()[estado_inicial]
closed ()
{}
while (open
no está vacía) {
remover
el primer estado X de la lista open
if (X
es un estado objetivo) return éxito
else
{
generar el conjunto de sucesores del
estado X
agregar
el estado X al conjunto closed
eliminar
sucesores que ya están en open o en closed
agregar
el resto de los sucesores al final de open
}
}
return
fracaso
}
Si el factor de
ramificación es B y la profundidad a la cual se encuentra el
estado objetivo más cercano es n, este algoritmo tiene una
complejidad en tiempo y espacio de O(Bn). Contrariamente a la
búsqueda en profundidad, la búsqueda en amplitud garantiza encontrar el camino
más corto.
Primero en profundidad (depthfirst).
·
Principio:
expandir el nodo más profundo que no haya sido expandido
·
La frontera es una
cola LIFO, i.e. nuevos sucesores van al inicio
Algoritmo:
1.-Crear una lista con un solo elemento consistente
en una trayectoria de longitud cero: el nodo raíz
2. Hasta que el primer camino de la lista llegue al
nodo objetivo o
se llegue a la lista vacía HACER
a. Extraer el primer camino de la lista
b. Expandir el nodo final de este camino.
c. Eliminar los ciclos de los caminos expandidos.
d. Insertar estos nuevos caminos al INICIO de la
lista
FIN Hasta
1. Si la lista está vacía, entonces NO hay
solución; Si no el primer
camino de la lista es la solución
Si el
conjunto open se maneja como una lista LIFO, es decir, como un
stack, siempre se estará visitando primero los últimos estados en ser
generados. Esto significa que si A genera B y C,
y B genera D, antes de visitar C se
visita D, que está más alejado de la raiz A, o sea más
profundo en el árbol de búsqueda. El algoritmo tiene en este caso la tendencia
de profundizar la búsqueda en una rama antes de explorar ramas alternativas.
procedure
Búsqueda_en_profundidad {
open ()
[estado_inicial]
closed ()
{}
while (open
no está vacía) {
remover
el primer estado X de la lista open
if (X
es un estado objetivo) return éxito
else
{
generar
el conjunto de sucesores del estado X
agregar
el estado X al conjunto closed
eliminar
sucesores que ya están en open o en closed
agregar
el resto de los sucesores al principio de open
}
}
return
fracaso
}
Considerando que
la cantidad promedio de sucesores de los nodos visitados es B (llamado
en inglés el branching factor y en castellano el factor
de ramificación), y suponiendo que la profundidad máxima alcanzada es n,
este algoritmo tiene una complejidad en tiempo de O(Bn) y, si
no se considera el conjunto closed, una complejidad en espacio de
O(B × n). En vez de usar el conjunto closed, el control
de ciclos se puede hacer descartando aquellos estados que aparecen en el camino
generado hasta el momento (basta que cada estado generado tenga un puntero a su
padre).
El mayor problema
de este algoritmo es que puede "perderse" en una rama sin encontrar
la solución. Además, si se encuentra una solución no se puede garantizar que
sea el camino más corto.
bibliografía
http://inteligenciaartificial-isc.blogspot.com/p/unidad-2.html
https://www.uv.mx/personal/edbenitez/files/2010/09/CursoIA10-II-2.pdf
Comentarios
Publicar un comentario