1. No category

Inteligencia Artificial
Búsqueda Informada (Universidad del Bío-Bío)
Búsqueda Informada
Universidad del Bío-Bío
Abril’2012
Inteligencia Artificial
Abril’2012
1 / 14
Contenido de esta Presentación
1
Búsqueda Informada
2
Estrategias de Búsqueda Informada
3
Búsqueda Beam
Algoritmo
Traza
4
Primero el mejor
5
Hill Climbing
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
2 / 14
Búsqueda Informada
Búsqueda informada
Cuando realizamos la búsqueda en un espacio de estados
podemos hacer dos cosas:
1
Buscar el estado final sin evaluar los estados sucesores.
Ejemplo: en el problema del 8 puzle hemos implementado la
búsqueda en anchura y en profundidad. Ambas son búsquedas
donde no realizamos ninguna evaluación sobre los estados que
vamos a generar. En el caso de profundidad queda demostrado que
dependiendo del orden de los movimientos encontraremos diferentes
soluciones.
2
Buscar el estado final calculando mediante evaluación cuál es el
mejor de los estados sucesores.
Ejemplo: en el problema del 8 puzle buscar alguna función que de
pistas sobre cuál es el mejor movimiento. Como veremos, una opción
es calcular el número de piezas descolocadas, aunque no es la
única.
Cuando no se evalúan los estados se habla de “búsqueda no
informada”, en caso contrario hablamos de “búsqueda
informada” o “búsqueda heurística”.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
3 / 14
Búsqueda Informada
Búsqueda informada
El mecanismo que permite evaluar los próximos estados se
denomina heurística o función de evaluación.
En general, su uso NO garantiza encontrar una solución óptima,
pero sí, una solución de buena calidad en tiempo razonable.
Se utiliza en problemas donde aparece la explosión
combinatoria ya que los algoritmos no informados tienen unos
costes inaceptables en tiempo y espacio.
Otras ventajas: normalmente no requerimos encontrar
soluciones óptimas, el caso peor no se suele dar y diseñar una
heurística nos proporciona mayor conocimiento del problema.
Las heurísticas se puede clasificar en generales o específicas.
Las generales son válidas para muchos problemas diferentes.
Las específicas para un problema particular.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
4 / 14
Búsqueda Informada
Búsqueda informada
Para buscar una función de evaluación específica es necesario
que se conozca el problema con precisión.
La función de evaluación se define en base a la experiencia,
conocimiento del problema, sentido común o intuición de quien
implementa el algoritmo y por tanto de esa función heurística.
Nuestra primera función de evaluación se basa en el número de
huecos que están descolocados.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
5 / 14
Búsqueda Informada
Búsqueda informada: Ejemplo 8 puzle
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
6 / 14
Estrategias de Búsqueda Informada
Estrategias búsqueda informada
Vamos a empezar el estudio de los algoritmos de búsqueda
informada.
Podemos clasificar los algoritmos en:
Informados en anchura:
Beam = Anchura + Heurística + Restricción de memoria.
Informados en profundidad:
Primero el mejor = Profundidad + Heurística.
Hill Climbing = Profundidad + Heurística + Mejoramiento y Avandono.
Hill Climbing Aleatorio
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
7 / 14
Búsqueda Beam
Beam Search
Aunque el algoritmo en anchura garantiza encontrar la solución
con menor profundidad, resulta inviable usarlo cuando el espacio
de estados es muy grande debido a su consumo de memoria .
Por esta razón, se desarrollo el algoritmo Beam. Su objetivo es
mejorar la búsqueda en anchura para que el consumo de
memoria no sea tan elevado.
Con el fin de lograr este objetivo, el algoritmo Beam utiliza una
función heurística y emplea una variable B, que especifica el
numero de estados que podrán almacenarse en cada nivel.
Por tanto el algoritmo almacena los B mejores estados en
función de dicha heuristica. La idea es que esta conduzca a la
solución y el peso para mantener a los mejores candidatos.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
8 / 14
Búsqueda Beam
Beam Search
1
2
3
Calcula los sucesores.
Selecciona cuáles son B estados mejores.
Expande los B.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
9 / 14
Búsqueda Beam
Beam Search
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
10 / 14
Búsqueda Beam
Algoritmo
Beam Search: Algoritmo
historialEstados={ estadoInicial };
colaEstados={ estado Inicial };
while ( !colaEstado.isEmpty() ) {
listaTemporal={ }; //lista ordenada
Estado temp;
for ( int i=0 ; i < colaEstados.size() ; i++ ) {
temp=colaEstados.get(i);
colaEstados.remove(0);
sucesores=getSucesores(temp);
for ( int j=0 ; j < sucesores.size() ; j++ ) {
sucesor=sucesores.get(j);
if ( sucesor == estadoFinal ) solución encontrada;
listaTemporal.add(sucesor);
}
}
colaEstados.clear();
while ( !listaTemporal.isEmpty() && B > colaEstados.size() ) { //construimos colaEstados para la
temp=listaTemporal.get(0);
listaTemporal.remove(0);
if ( temp no esta en historial ) {
historialEstados.add(temp);
colaEstados.add(temp);
}
}
}
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
11 / 14
Búsqueda Beam
Traza
Beam Search: Traza
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
12 / 14
Primero el mejor
Primero el mejor
1
2
3
Calcula los sucesores.
Selecciona cuáles es mejor.
Lo Expande.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
13 / 14
Hill Climbing
Hill Climbing
Es una variante del algoritmo “primero el mejor”.
Usa una técnica de mejoramiento iterativo.
Solo seguimos si el siguiente mejor estado es mejor que el
anterior.
El método termina cuando no se mejora.
Puede que nunca lleguen a encontrar una solución.
Búsqueda Informada (Universidad del Bío-Bío)
Inteligencia Artificial
Abril’2012
14 / 14