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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
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.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes 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 these notes for $7.16. You're not tied to anything after your purchase.
