Algoritmo a*
En
? ¿Cómo saber si una posibilidad es prometedora?
- A través de la función f (x) = g (x) + h (x)
- Que es una función heurística
- g (x) es el costo de, desde el origen, alcanzar el nodo x
- h (x) es una función heurística para estimar el costo del siguiente nodo
- Siempre observamos las posibilidades de expandir el árbol y calculamos el valor de f (x)
- Agregamos el nodo que tiene la f (x) más pequeña entre aquellos que encontramos
- OA* es el algoritmo más eficiente para las maneras mínimas en los gráficos
- Sin embargo, son limitaciones severas
- Es necesario definir una h (x) que sea admisible: nunca devolverá un valor mayor que la distancia real de x a y
- Si H (x) es admisible, pero demasiado subestimada la distancia real, el algoritmo es súper ineficiente. Si h (x) no es admisible, el algoritmo puede no encontrar la forma mínima
? Complejidad
- La complejidad depende directamente de la función h (x) utilizada.
- En el peor de los casos, la cantidad de nodos explorados es exponencial en el tamaño de la ruta más pequeña, pero tiene complejidad polinomial si h ∗ (x) −H (x) ≤o (logh ∗ (x)).
? ¿Cuándo es bueno usarlo?
- Gráficos donde uno puede subestimar la distancia entre dos vértices, como en los mapas
- La distancia más corta entre dos puntos es una línea, pero probablemente la distancia real será mayor que eso
? ¿Cuál es la forma mínima en este caso?
Ejecutar el proyecto
Resultado
Autores
Licencia
Este proyecto está bajo el MIT. Vea aquí para obtener más información.
