2.2.
2 Búsqueda primero en anchura
Búsqueda en anchura es un algoritmo para recorrer o buscar elementos de un grafo (usado
frecuentemente en arboles). Se comienza por la raíz y se explora todos los hijos de este
nodo. A continuación, se explora cada uno de los hijos de los hermanos y así sucesivamente
hasta encontrar la solución.
PSeudocódigo Algoritmo:
Establecer nodo origen
Evaluar primer hijo
si cumple, establecer como origen y salir
si valido, repetir búsqueda a partir del nuevo estado
sino valido, repetir búsqueda para todos los hermanos
si encuentra , establecer como origen y salir
si no encuentra, marcar al padre como no valido
establecer origen como abuelo y seguir buscando.
Estrategias de Búsqueda Ciega
Búsquedas ciegas o no informadas: estrategias de búsqueda de soluciones que no explotan
información adicional que pueda guiar el proceso
Estrategias básicas Búsqueda Primero en Anchura Dr. Edgard I. Benítez G. Inteligencia
Artificial 2 Búsqueda Primero en Anchura Búsqueda Primero en Profundidad
Otras estrategias derivadas Búsqueda de Costo Uniforme Búsqueda de Profundidad
Limitada Búsqueda Primero en Profundidad con Profundidad Iterativa
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:
primero en anchura
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.
Búsqueda primero en anchura. Ejemplo:
2.2.3 Búsqueda en profundidad iterativa
Una búsqueda en Profundidad Iterativa (BPI) es un algoritmo de búsqueda no
informada utilizado para una estrategia de búsqueda en el espacio de estados en la que se
realizan sucesivas búsquedas en profundidad limitada incrementando el límite de
profundidad en cada iteración hasta alcanzar d ,La profundidad del estado objetivo de
menor profundidad.
BPI es equivalente a la búsqueda en anchura, pero usa mucha menos memoria; en cada
iteración, visita los nodos del árbol de búsqueda en el mismo orden que una búsqueda en
profundidad, pero el orden en el que los nodos son visitados finalmente se corresponde con
la búsqueda en anchura.
BPI combina la eficiencia del espacio de estados de la búsqueda en profundidad y la
completitud de la búsqueda en anchura (cuando el factor de ramificación es finito). Es
óptima cuando el costo del camino es una función no decreciente de la profundidad del
nodo.
La complejidad en espacio de la BPI es { O(bd)}, donde { b} es el factor de ramificación
y { d} es la profundidad de la solución más superficial. Dado que BPI visita los estados
múltiples veces, puede parecer extremadamente costoso, pero no lo es, dado que la mayor
parte de los nodos se encuentran en el nivel más profundo del árbol, por lo tanto, no tiene
mucha importancia que se visiten los niveles superiores varias veces.
La principal ventaja de BPI en búsquedas en árboles de juegos es que las búsquedas
anteriores tienen a mejorar la heurística usada, como heurística asesina o la poda alfa-beta,
de forma que se puede obtener una estimación más precisa de la puntuación de varios
nodos en la última búsqueda y la búsqueda se completa más rápidamente ya que se hace en
un orden mejor. Por ejemplo, la poda alfa-beta es más eficiente si se busca el primer
movimiento mejor.
Una segunda ventaja es la complejidad en tiempo del algoritmo. Porque las primeras
iteraciones usan valores pequeños para {d}, es decir, se ejecutan extremadamente rápido.
Esto permite al algoritmo proporcionar indicaciones sobre el resultado casi
inmediatamente, refinándolas según { d} aumenta. Cuando se utiliza en un entorno
interactivo, como en un programa para jugar al ajedrez, esta facilidad permite al programa
jugar en cualquier momento con la mejor solución encontrada hasta el momento en la
búsqueda realizada.
La complejidad en tiempo en un árbol equilibrado es la misma en con búsqueda en
profundidad: { O(b{d})} .
En una búsqueda en profundidad iterativa, los nodos en el nivel más inferior se expanden
una sola vez, los del nivel anterior dos veces y así hasta la raíz del árbol, que se
expande { d+1} veces.
En resumen, una BPI de profundidad 1 a profundidad {d} expande, aproximadamente,
un 11% más de nodos que una búsqueda en anchura simple o una búsqueda con
profundidad limitada de profundidad {d}, cuando { b=10}. Cuanto mayor es el factor de
ramificación, menor es la sobrecarga de estados expandidos múltiples veces, pero incluso
para un factor de ramificación 2, la BPI solo necesita el doble que una búsqueda en
anchura. Esto significa que la complejidad de la BPI es aún { O(b^{d})}, y la complejidad
en espacio es { O(d)} como una búsqueda en profundidad simple. En general, BPI es el
método de búsqueda principal cuando hay un espacio de estados grande y la profundidad de
la solución es desconocida.
Una búsqueda en profundidad empezando en A, asumiendo que los lados izquierdos del
gráfico se toman antes que los derechos y asumiendo que la búsqueda recuerda los nodos
visitados previamente y no los repite (dado que esto es un pequeño grafo), visitará los
nodos en el siguiente orden: A, B, D, F, E, C, G.
Realizando la misma búsqueda sin recordar los nodos previamente visitados, el resultado
no tendrá fin: A, B, D, F, E, A, B, D, F, E, etc., esto ocurre por el ciclo entre A, B, D, F y E,
lo que no permite alcanzar C o G.
La búsqueda en profundidad iterativa nos soluciona estos bucles y alcanzará los nodos de
los siguientes niveles. Asumiendo que procede de izquierda a derecha como antes:
0: A
1: A (repetido), B, C, E
(Nótese que BPI ha visitado C, lo que no ocurre con la búsqueda en profundidad.)
2: A, B, D, F, C, G, E, F
(Nótese que aún visita C, pero aparece más tarde. También visita E por un camino distinto,
pero vuelve a F dos veces.)
3: A, B, D, F, E, C, G, E, F, B
Para este grafo, cuanta más profundidad se añade, los ciclos "ABFE" y "AEFB"
simplemente se alargan antes de que el algoritmo abandone e intente otra rama. Puede
recorrer varias veces al mismo nodo siempre y cuando no sea la solución
Algoritmo
El siguiente pseudocódigo muestra una BPI implementada en términos de una búsqueda en
profundidad limitada recursiva. (LLamada BP).
BPI(raíz, objetivo)
{
profundidad = 0
repetir
{
resultado = BPL(raíz, objetivo, profundidad)
Si (resultado es una solución)
devolver resultado
profundidad = profundidad + 1
}
}
Una búsqueda en profundidad limitada se puede implementar de forma recursiva como
sigue. Nótese que solo tiene que comprobar los nodos objetivos cuando profundidad == 0,
porque cuando profundidad > 0, BPL expande nodos que han sido visitados en iteraciones
previas de BPI.
BPL(nodo, objetivo, profundidad)
{
Si (profundidad == 0 y nodo == objetivo)
devolver nodo
sino si (profundidad > 0)
para cada hijo en expandir(nodo)
resultado = BPL(hijo, objetivo, profundidad-1)
si resultado distinto de null
devolver resultado
sino
devolver null
}
4.2 Métodos de aprendizaje
Los árboles de decisión son uno de los métodos de aprendizaje inductivo más usado.
Hipótesis de aprendizaje inductivo: cualquier hipótesis encontrada que clasifique un
número suficientemente grande de ejemplos de entrenamiento clasificará otros
ejemplos no observados.
Razonamiento deductivo: partiendo de unas premisas se llega necesariamente a una
conclusión. No aporta información nueva.
Razonamiento abductivo: partiendo del conocimiento de unos efectos (síntomas) se
llega a la causa (enfermedad)
● Se trata de aproximar una función desconocida a patir de ejemplos positivos y negativos
de esa función. Esos ejemplos serán en realidad pares , donde x es el valor de entrada y f(x)
el valor de la función aplicada a x.
● Dado un conjunto de ejemplos de f, la inducción consiste en obtener una función h que
aproxime f. A esta función h se la denomina hipótesis
Arboles de Decisión
● Pueden ser leídas como conjunto de reglas (en el caso de abajo tres)
● En un árbol de decisión cada nodo del árbol es un atributo (campo) de los ejemplos, y
cada rama representa un posible valor de ese atributo