UNIVERSIDAD DE LA RIOJA
Postgrado al que pertenece: Máster Universitario en Inteligencia Artificial
Denominación de la asignatura: Razonamiento y Planificación Automática
Guía de Estudio: TEMA 4. Búsqueda no informada
UNIVERSIDAD DE LA RIOJA
Postgrado al que pertenece: Máster Universitario en Inteligencia Artificial
Denominación de la asignatura: Razonamiento y Planificación Automática
Guía de Estudio: TEMA 4. Búsqueda no informada
Introducción
La búsqueda no informada es un enfoque fundamental en inteligencia artificial para la resolución
de problemas donde no se dispone de información adicional sobre el espacio de estados más allá
de la definición del problema mismo. Este tipo de búsqueda se basa en explorar sistemáticamente
todos los posibles estados hasta encontrar una solución. En este tema, se abordarán las técnicas
de búsqueda en amplitud, búsqueda en profundidad y búsqueda de coste uniforme, explorando
sus características, ventajas y desventajas.
a. ¿Cómo estudiar este tema?
Para estudiar la búsqueda no informada, es esencial tener una comprensión sólida de los
conceptos básicos de grafos y algoritmos. Los pasos recomendados incluyen:
1. Revisar los conceptos de grafos: Asegúrese de entender nodos, aristas, grafos dirigidos
y no dirigidos.
2. Estudiar algoritmos básicos: Familiarícese con algoritmos simples y cómo se aplican a
grafos.
3. Implementar ejemplos prácticos: Utilice lenguajes de programación como Python para
implementar y visualizar los algoritmos.
4. Analizar casos de uso: Examine problemas prácticos y cómo las diferentes técnicas de
búsqueda no informada pueden resolverlos.
b. Descripción general de un problema de búsqueda
Un problema de búsqueda se define por:
Estado Inicial: El punto de partida en el espacio de búsqueda.
Estados Meta: Los posibles estados de destino que son soluciones al problema.
Operadores: Conjunto de acciones que permiten transitar de un estado a otro.
Función de Costo: En algunos problemas, cada transición puede tener un costo asociado.
c. Búsqueda en amplitud
Definición: La búsqueda en amplitud (BFS) explora sistemáticamente todos los nodos a un nivel
determinado antes de pasar al siguiente nivel.
Características:
Utiliza una cola para mantener los nodos a explorar.
, Garantiza encontrar la solución más corta si todos los operadores tienen el mismo costo.
Ventajas:
Completa: Siempre encuentra una solución si existe.
Óptima: Encuentra la solución más corta en términos de número de pasos.
Desventajas:
Alta complejidad espacial: Almacena todos los nodos en memoria.
Puede ser muy lenta en grafos grandes.
d. Búsqueda en profundidad
Definición: La búsqueda en profundidad (DFS) explora tan profundo como sea posible a lo largo
de cada rama antes de retroceder.
Características:
Utiliza una pila para mantener los nodos a explorar.
No garantiza encontrar la solución más corta.
Ventajas:
Baja complejidad espacial: Almacena solo el camino actual y los nodos adyacentes.
Más eficiente en términos de tiempo en grafos profundos con pocas soluciones.
Desventajas:
No completa: Puede quedar atrapada en bucles infinitos en grafos con ciclos.
No óptima: No necesariamente encuentra la solución más corta.
e. Búsqueda de coste uniforme
Definición: La búsqueda de coste uniforme (UCS) expande el nodo con el menor costo
acumulado desde el nodo inicial.
Características:
Utiliza una cola de prioridad basada en el costo acumulado.
Similar a BFS, pero tiene en cuenta los costos de transición.
Ventajas:
Completa: Siempre encuentra una solución si existe.
Óptima: Encuentra la solución de costo mínimo.
Desventajas:
Alta complejidad espacial y temporal: Similar a BFS, puede requerir grandes cantidades de
memoria y tiempo.
Los beneficios de comprar resúmenes en Stuvia estan en línea:
Garantiza la calidad de los comentarios
Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!
Compra fácil y rápido
Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.
Enfócate en lo más importante
Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable.
Así llegas a la conclusión rapidamente!
Preguntas frecuentes
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
100% de satisfacción garantizada: ¿Cómo funciona?
Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ma_medina. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for 6,78 €. You're not tied to anything after your purchase.