Supongo que está preguntando sobre la caminata más corta, porque la solución al problema de cualquier caminata es trivial, como ya se señaló en los comentarios, DFS sería suficiente.
Y para el problema sobre la caminata más corta: no creo que pueda encontrar alguna solución que sea significativamente mejor que Bitmask DP.
Suponga que todos los bordes tienen un costo 1. Si sabe cómo verificar que la respuesta a su problema es N-1 (caminar sin repeticiones), sabe cómo verificar que el gráfico dado contiene la ruta hamiltoniana que comienza en el nodo 1. Esto significa que su problema es al menos tan difícil como el problema del camino hamiltoniano (porque una buena solución a su problema nos dará una buena solución al problema del camino hamiltoniano ; puede probar todos los puntos finales posibles con su problema original y le dirá la respuesta para el problema del camino hamiltoniano ).
- Un k-palíndromo es una cadena que se transforma en un palíndromo al eliminar como máximo k caracteres de él. Dada una cadena S y un número entero K, ¿encuentra si S es un k-palíndromo o no? Restricciones: S tiene como máximo 20,000 caracteres y 0 <= k <= 30
- ¿Por qué las funciones de límite superior e inferior en C ++ STL dan diferentes índices para el mismo número?
- ¿Cuáles son algunas de las estructuras de datos / algoritmos de clasificación más interesantes?
- ¿Hay algún algoritmo de ordenación que funcione en el orden de n?
- ¿Cuáles son algunos algoritmos nuevos e interesantes en bioinformática / informática genómica?
El problema del camino hamiltoniano es NP completo ; hasta ahora no se ha encontrado una solución de tiempo polinómico para este tipo de problemas. Esto implica que la solución de tiempo polinómico para su problema también no se conoce hoy en día.
