Scribd
Cargar
25 vistas3 páginas

Algoritmo A* en Grafos: Ejercicios Prácticos

El documento describe dos problemas de ruta óptima que involucran grafos y el algoritmo A*. El primer problema involucra encontrar la ruta más corta en un grafo desde el nodo A al nodo J aplicando A* paso a paso. El segundo problema involucra encontrar la ruta más corta entre Turín y Nápoles usando heurísticas de distancia y A*.

Cargado por

LUIS GONZALEZ RIQUELME
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
25 vistas3 páginas

Algoritmo A* en Grafos: Ejercicios Prácticos

El documento describe dos problemas de ruta óptima que involucran grafos y el algoritmo A*. El primer problema involucra encontrar la ruta más corta en un grafo desde el nodo A al nodo J aplicando A* paso a paso. El segundo problema involucra encontrar la ruta más corta entre Turín y Nápoles usando heurísticas de distancia y A*.

Cargado por

LUIS GONZALEZ RIQUELME
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Pontificia Universidad Católica de Valparaíso

Facultad de Ingeniería
Escuela de Ingeniería Informática

Ay. Etienne Bellenger

Ayudantía 4 - ICI 5240


1. Considere el grafo de la Figura 1, donde el nodo inicial es A y donde los nodos meta
es J. Cada arco u operador lleva asociado su coste y en cada nodo aparece (en rojo)
una estimación de heurística ℎ(𝑛). Aplique paso a paso el algoritmo A* al grafo
dado, indicando de forma razonada la siguiente información en cada paso del
algoritmo:

i. Qué nodo es expandido


ii. Cuál es el contenido de ABIERTA tras la expansión del nodo, indicando el
valor de la función de evaluación heurística para cada nodo de ABIERTA

Figura 1. Grafo de búsqueda en el que el nodo inicial es A y el nodo meta es J.


Pontificia Universidad Católica de Valparaíso
Facultad de Ingeniería
Escuela de Ingeniería Informática

Ay. Etienne Bellenger

2. Un viajero desea realizar un circuito para trasladarse entre dos ciudades de la mejor
manera posible. En la Figura 2, se muestra el grafo que representa la situación del
problema. Las etiquetas de las aristas del grafo representan la distancia en kilómetros
entre los pares de ciudades de los extremos. El viajero se encuentra en Turín en el
momento inicial de la búsqueda y desea trasladarse a Nápoles con el menor coste
kilométrico que sea posible.

Figura 2. Grafo de búsqueda en el que el nodo inicial es Turín y el nodo meta es Nápoles.
Pontificia Universidad Católica de Valparaíso
Facultad de Ingeniería
Escuela de Ingeniería Informática

Ay. Etienne Bellenger


Ejercicios a resolver.

i. Resuelva el problema mediante el empleo de métodos heurísticos, se requiere


la información que estime las distancias entre cada una de las distancias entre
cada una de las ciudades del mapa y ciudad objetivo, Nápoles.

Turín 893 Pisa 571


Milán 774 Forlí 557
Pavía 764 Florencia 473
Venecia 734 Siena 437
Parma 658 Roma 226
Padua 695 Nápoles 0

ii. Resuelva el problema mediante el empleo del algoritmo A*

Referencias
[1] Fernández Orchando, J. M. (2018). Cálculo de trayectos mediante algoritmos de búsqueda
informada sobre grafos ponderados no dirigidos.

También podría gustarte