Algoritmo A* para encontrar la ruta óptima de Colonia a Karlsruhe.

Question

El Algoritmo A* le ayuda a encontrar la ruta óptima desde el punto A à B en un plano gráfico determinado. Digamos que tengo el siguiente problema en el que tengo que pasar de Colonia à Karlsruhe .

Sin llegar a escribir un algoritmo, intenté encontrar la ruta óptima encontrando la distancia mínima desde el punto A à B . Pasé de Colonia à Frankfurt à Kaiserlautern à Ludwigshafen à Karlsruhe donde la distancia total termina siendo $912$ unidades. La pregunta es que si se diseñara un hipotético algoritmo, ¿qué ciudades comprobaría? Creo que debería comprobar todas las ciudades que están conectadas directamente con la ciudad de partida (y luego las ciudades que están en la ruta óptima), así que Metz, Saarbrücken y Frankfurt. Mi respuesta es correcta excepto para Metz que es no una ciudad que el algoritmo "visitaría"?

Así que tengo $3$ preguntas:

1. ¿Por qué Metz no ¿es correcto?
2. ¿Es correcto mi valor de distancia?
3. ¿Qué hace el $h$ -¿El valor nos dice?

P.D. - Sé que esto es material teórico básico de CS, pero sólo estoy en mi primer semestre, así que por favor tenga piedad :)

Answer 1

El $h$ -son límites inferiores razonables para la distancia a los destinos finales. (El ejemplo canónico es la distancia medida a lo largo de una línea recta). no incluyen el $h$ -en el coste total, por lo que la respuesta a su pregunta 2 es no, su valor de distancia no es correcto. La distancia total real se obtiene sumando las distancias entre las sucesivas ciudades a lo largo del camino elegido. El $g$ -se actualizan durante el algoritmo, y en cada paso, son las distancias más cortas desde el punto de partida encontradas hasta el momento. Así, una vez que el valor de $g(n)$ se ha encontrado el valor $f(n)=g(n)+h(n)$ es un límite inferior para el coste total de un camino que pasa por el nodo $n$ . En cada paso del algoritmo, se "comprueba" el nodo que tiene el menor $f$ -valor entre los nodos que aún no han sido comprobados. Comprobar un nodo significa actualizar el $g$ -valores de sus vecinos. Cuando se comprueba el destino, el algoritmo termina. Metz nunca se comprueba porque su $f$ -es mayor que el coste del camino óptimo, que es igual al $f$ -valor del destino.

Answer 2

• El algoritmo A* utiliza las distancias reales entre vecinos, junto con las distancias estimadas ( $h$ ), para encontrar el camino más corto. Si las estimaciones son buenas, se garantiza que A* encuentre el camino más corto.

• A mano, has encontrado el camino más corto entre Colonia y Karlsruhe. Si las estimaciones son buenas, se garantiza que A* encuentre ese camino (u otro de igual longitud). La longitud de su camino es de 430 que se puede calcular sumando las longitudes de las carreteras entre las ciudades. Creo que has añadido $h$ valores por error, pero $h$ no afectan a la longitud. Se utilizan para guiar la búsqueda, pero no se incluyen cuando se calculan las longitudes de las rutas. (Explico $h$ valores más abajo).

• Lo principal que hay que saber de A* es que mantiene una lista de caminos parciales, y que decide qué camino considerar (ampliar) a continuación en función de longitud total estimada del recorrido hasta la meta .

  La longitud total estimada del camino es la longitud del camino hasta el momento, más la distancia estimada restante hasta la meta. El $h$ le indican la distancia estimada de cada ciudad a la meta.

• Inicialmente, A* calculará la longitud total estimada del trayecto desde Colonia hasta sus vecinos de Karlsruhe. Esas estimaciones son:

  • Köln-Frankfurt 190 + 125 = 315
  • Köln-Saarbrücken 260 + 105 = 365
  • Köln-Metz 290 + 162 = 452

• Así que, naturalmente, A* explora primero las rutas que van de Colonia a Fráncfort. Si las estimaciones son buenas, los caminos con la menor longitud total estimada tenderán a tener la menor longitud real cuando lleguen a la meta.

• A continuación, A* calcula los costes de Colonia-Frankfurt-Koblenz y de los demás vecinos. También recuerda los otros trayectos que ha calculado: Colonia-Saarbrücken y Colonia-Metz. Considerará el trayecto que tenga la menor longitud entre los que ha calculado.

• La razón por la que A* nunca visita Metz es porque el camino hacia Colonia-Metz nunca tiene la longitud de camino más corta estimada . Esto se puede comprobar calculando las longitudes estimadas del camino más corto real:

  Colonia-Frankfurt, Colonia-Frankfurt-Kaiserlautern, Colonia-Frankfurt-Kaiserlautern-Ludwigshafen, Colonia-Frankfurt-Kaiserlautern-Ludwigshafen-Karlsruhe

  Todos ellos tienen estimaciones más bajas que Köln-Metz, por lo que el objetivo se encontrará antes de visitar Köln-Metz.