Los problemas básicos de optimización se pueden resolver a través de Dijkstra, si necesita una distancia de menor costo entre el origen y el destino, el TSP sería mejor utilizando matrices que contengan todas las distancias alternativas entre el Punto A y el Punto B. Aunque esto no es escalable sino solo métodos viables.
Algún grupo de intelectuales piensa que, A * heurística es mejor que Dijkstra. Una simple heurística A * utiliza la distancia geométrica al destino dividida por la máxima velocidad de viaje posible.
Por lo tanto, A * procederá buscando rutas que se dirijan en la dirección correcta. Dijkstra es terrible porque estúpidamente busca en todas las direcciones.
- ¿Qué debo hacer después de aprender Java central y resolver problemas de algoritmos y estructura de datos en HackerRank, CodeChef, etc.?
- Cómo imprimir todas las permutaciones de una cadena tanto de forma iterativa como recursiva
- ¿Qué es un promedio móvil y, algorítmicamente, cómo se calcula dicho conjunto?
- Cómo hacer un proyecto de chatbot
- ¿Cuál es el número total de rompecabezas de sudoku posibles?
El truco es el cálculo previo, incluso Google tiene un gran procesamiento previo de datos cuantificables. Una implementación rápida del algoritmo no modificado de Dijkstra necesita aproximadamente 10 segundos. mientras que el cálculo previo puede acelerar el proceso, donde con los algoritmos actuales se pueden calcular las rutas más cortas en un tiempo considerablemente menor que 1 m-seg.
Con los años, este tema es muy activo en la investigación. Reflexione sobre los siguientes trabajos de investigación y enlaces de video.
Ingeniería Algoritmos de planificación de rutas rápidas
Calcular rutas más cortas de muchos a muchos utilizando jerarquías de autopistas.
http://algo2.iti.kit.edu/routeplanning.php
https://www.youtube.com/watch?v=-0ErpE8tQbw
http://research.microsoft.com/pubs/60764/tr-2005-132.pdf
