Como otros ya notaron, esta es una versión del problema del vendedor ambulante. Sin embargo, a las otras respuestas les falta el hecho de que con solo 18 puntos de control podemos encontrar fácilmente la solución óptima, en un segundo en una computadora común.
En primer lugar, precalcule las distancias entre el inicio, el objetivo y cada uno de los puntos de control. Esto se puede hacer fácilmente mediante una búsqueda de amplitud.
Luego, use el algoritmo de programación dinámica [matemática] O (n ^ 2 2 ^ n) [/ matemática] para resolver el TSP. Esta es, en esencia, otra búsqueda de ruta más corta, pero esta vez tenemos vértices [matemáticos] O (n2 ^ n) [/ matemáticos] en nuestro gráfico. Cada vértice corresponde a un posible estado en el que podemos estar. Cada estado es un par (S, v), donde S es el conjunto de vértices que ya visitamos, y v es el vértice que visitamos por última vez. (En el programa, S puede representarse fácilmente con una máscara de bits). Y todo lo que necesitamos es el camino más corto desde ({inicio}, inicio) hasta (todo, objetivo).
- ¿Qué algoritmos puedo usar para predecir la temperatura o dichos parámetros en función de sus datos históricos?
- Dado un conjunto etiquetado de nodos, ¿podemos 'siempre' construir un árbol de búsqueda binario (BST) para ellos?
- ¿Hay alguna prueba de que los algoritmos de clasificación no pueden tener una complejidad mejor que O (Nlog (N))?
- Cómo explicar el algoritmo de clasificación de inserción a un niño de 10 años
- ¿Dónde puedo encontrar una biblioteca de estructura de datos de gráficos dirigida, implementada en Javascript?
