El algoritmo A *, también conocido como Best First Search, es un tipo de búsqueda que utiliza una heurística (una heurística admisible es aquella que nunca sobreestima el costo de llegar al final desde ese punto) para decidir de qué manera se debe expandir una ruta. Para calcular la heurística usualmente hacemos distancias de distancia + heurística = prioridad. Cualquier punto que tenga el valor de prioridad más bajo es el nodo que se atraviesa al siguiente.
Típicamente, el algoritmo A * se usa típicamente para gráficos y recorridos de gráficos. En términos de gráficos, A * se usa para encontrar la ruta más corta a un cierto punto desde un punto dado. Esto se puede extender al mundo real, se usa para enrutar. Creo que Google Maps y otros servicios de enrutamiento similares utilizan el algoritmo A * para encontrar el camino que debe tomar para minimizar su tiempo en el camino. En ese caso, la heurística suele ser la distancia física * algún factor de tráfico. El algoritmo puede usarse para varios otros efectos secundarios de este problema, como los juegos en los que desea encontrar el camino más corto a través de un laberinto o “juegos de escalera de palabras”
A * es básicamente la forma en que podemos enrutar tan rápido. Al evitar malas decisiones, podemos ahorrar tiempo (y memoria) y también tomar el camino correcto.
- En un gráfico no dirigido, ¿cuál es el grado de un vértice con un bucle automático?
- ¿Cuáles son los 5 mejores algoritmos esenciales (excepto la clasificación) que todo programador debe saber?
- ¿Qué es particionar en chispa, por qué lo necesitamos?
- Si saco el bucle for más interno de un bucle for anidado y lo ejecuto solo, ¿cambiará la complejidad del tiempo?
- Cómo mostrar que O (max {f (n), g (n)}) = O (f (n) + g (n))
