Una manera simple de extender su solución es ejecutarla en todas las permutaciones de longitud 2, luego longitud 1, y dar el mejor salto en los tres bucles. Cuando N = 3 casi cualquier solución es lo suficientemente buena. 🙂
La otra forma en que puedo pensar en hacer una búsqueda exhaustiva es tratar el problema como un gráfico y usar la búsqueda en profundidad para examinar todas las opciones. (Técnicamente, estaría haciendo DFS en el árbol de decisión de posibles rutas, ya que puede visitar cada roca varias veces durante la búsqueda). En psuedocode:
dfs (currentLocation, visitado):
si currentLocation es el banco opuesto:
volver (mejor salto 0, camino vacío)
para cada roca R que no está en el conjunto visitado: // trata aquí el banco opuesto como una roca
(maxHop, ruta) = dfs (R, visitado + ubicación actual)
salto = distancia (currentLocation, R)
ruta = [R] + ruta
si hop> maxHop entonces maxHop = hop
encontrar el mejor salto, par de ruta sobre todos los R
volver (mejor salto, mejor camino)
- ¿Cuáles son las mejores prácticas para implementar la paginación en un sitio web con una gran cantidad de datos?
- ¿Por qué no hay soluciones a pedido de Hadoop para múltiples inquilinos?
- ¿Cuáles son los algoritmos necesarios para resolver todos los problemas (usando C ++) en cualquier concurso de codificación competitivo?
- ¿Cuáles son los algoritmos más utilizados en los que puedo confiar para mejorar mis habilidades de resolución de problemas?
- ¿Cuáles son algunos algoritmos rápidos de descenso de gradiente?
Ahora, ciertamente es posible mejorar esto. Tenga en cuenta que si es más corto de R a la orilla que a cualquier otra roca, entonces ningún mejor camino visitaría R y luego saltaría a otro lugar que no sea la orilla. Y si el mejor camino desde R hasta la orilla se ha identificado sin rocas visitadas, entonces la respuesta será la misma siempre que el conjunto visitado no incluya rocas del mejor camino. Esto puede podar bastante del árbol de búsqueda.
¿Es posible llegar a un mejor algoritmo? Originalmente pensé que sí, pero no parece haber ninguna manera de determinar el mejor camino desde cada piedra en un orden fácil de definir.
