Inteligencia Artificial

Preguntas

Características principales de:

Métodos de búsqueda heurísticos o informados:

No garantizan que se encuentre una solución, aunque existan soluciones.

Si encuentran una solución, no se asegura que ésta tenga las mejores a propiedades (que sea de longitud mínima o de coste óptimo).

En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.

Métodos de búsqueda óptimos:

Analizar primero los nodos con menor coste.

Ordenar la cola de abiertos por coste, de menor a mayor de esta manera, cuando se llega por primera vez a un estado final, se llega con el menor coste posible.

Se trata de una búsqueda ciega:

No usa conocimiento para guiar la búsqueda hacia el objetivo

Caso particular: búsqueda en anchura.

Es completa.

Siempre encuentra solución óptima.

Salvo en espacios de estados pequeños, en la práctica esta búsqueda no es posible, debido a la cantidad de tiempo y espacio que necesita

Cuáles son las similitudes y diferencias, si es que las hay, entre:

Método de búsqueda de ascenso de colina y método de búsqueda en haz.

Método en ascenso de colina Método en haz

Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese momento.

Se dividen en dos grupos:

Los métodos irrevocables, que no prevén la vuelta a un lugar del espacio de estados si el camino resulta inadecuado.

Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos que el camino elegido no es el más adecuado. Mantienen en memoria un número limitado de K nuevos sucesores.

Mantienen el camino: variante de primero el mejor

Mantienen el estado: variante de mejora iterativa (búsqueda en haz local).

No garantiza solución óptima.

Generalmente, mejor comportamiento que escalada con reinicio aleatorio k-veces: se comparte información útil entre los elementos de la población.

Método de búsqueda de ramificación y poda y A*.

Método de ramificación y poda Método A*

Al igual que los métodos de búsqueda con retroceso:

Se aplica a problemas de optimización con restricciones (algunas veces también a probl. de decisión)

Se genera el espacio de soluciones, organizándolo en un árbol.

Se podan subárboles inútiles.

Es un método completo de búsqueda, es decir, termina encontrando la solución cuando ésta exista para cualquier tipo de grafos.

Es admisible. Es decir, no sólo encuentra la solución sino que la que encuentra es la optima si se cumple la siguiente condición:

Para todo n h(n) es menor o igual que h*(n), es decir, si la función heurística que estima la distancia a la meta nunca puede superar la distancia real existente entonces A* garantiza encontrar la solución óptima.

Que ocurre en estos métodos de búsqueda en relación a :

El tiempo de búsqueda.

Memoria utilizada.

Puede llegar a que se encuentre una solución, cuando ocurriría esto si esto es posible.

Son estos métodos completos. ¿Por qué? Explique su respuesta.

Métodos informados Método óptimos

Tiempo de búsqueda En ascenso de colina: se debe recorrer el nodo con mejor nivel

En Haz: Entre más alta sea la W se obtendrá un mayor tiempo de búsqueda. O(rp) (se deben recorrer todos los nodos) R = factor de ramificación P= profundidad de la solución.

Memoria utilizada En ascenso de colina: Se utiliza un mínimo de memoria ya que el nodo que es descartado se elimina de la búsqueda.

En Haz: Entre más alta sea la W más memoria se necesitara O(rp) (se deben almacenar todos los nodos)R = factor de ramificación P= profundidad de la solución.

Solución No garantizan que se encuentre una solución, aunque existan soluciones Siempre encuentra solución óptima.

Método completo Sí, es completa Si, es completa

Que tipos de estructura utilizaría para implementar estos métodos de búsqueda, porque las utilizaría. Justifique su respuesta.

Método de Colina: Utiliza una estructura de datos del nodo actual que necesita solo el registro del estado y su valor de función objetivo.

Método de Haz: Comienza con estados generados aleatoriamente.

...