Estoy tratando de resolver una versión ligeramente modificada de laHamiltonian Path problema. Se modifica porque se nos dan los puntos de inicio y fin y, en lugar de determinar si existe una solución, queremos encontrar elnúmer de soluciones (que podrían ser 0).

El gráfico se nos proporciona como una matriz 2D, siendo los nodos los elementos de la matriz. Además, solo podemos movernos horizontal o verticalmente, no diagonalmente. No hace falta decir que no podemos ir de una ciudad a dos ciudades porque para eso tendríamos que visitar una ciudad dos veces.

Escribí una solución de fuerza bruta que intenta los 4 movimientos posibles (3 o 2 para los nodos en los bordes) en cada nodo y luego cuenta el número de soluciones (que es cuando alcanza la meta y también ha visto todos los otros nodos), pero funcionó durante cantidades ridículas de tiempo en entradas de tamaño modesto (como, por ejemplo, una matriz de 7x7).

También pensé en usarbúsqueda direccional ya que conocemos el objetivo, pero esto realmente no ayudó, ya que no solo queremos que las franjas se cumplan, también queremos asegurarnos de que se hayan visitado todos los nodos. Además, podría ser que cuando todos los nodos se hayan agotado entre las dos franjas, terminen de tal manera que no se puedan unir.

Siento que hay algo que no sé que me está dejando solo con una solución de fuerza bruta. Sé que el problema en sí es NP-completo, pero me pregunto si hay alguna mejora con respecto a la fuerza bruta. ¿Alguien puede sugerir algo más?

--Editar-

Mencioné que el uso de la búsqueda bidireccional realmente no ayuda y me gustaría aclarar por qué lo creo. Considere un gráfico de 2x3 con los nodos superior izquierdo e inferior derecho como el inicio y el objetivo, respectivamente. Deje que los márgenes de la búsqueda bidireccional se muevan hacia la derecha desde el inicio y hacia la izquierda desde el objetivo. Después de 2 movimientos, todos los nodos habrían sido visitados, pero no hay forma de unir las franjas, ya que solo podemos ir en una dirección desde un nodo. Sin embargo, podría ser posible hacer que el algoritmo funcione con algunas modificaciones, como señaló David en su respuesta a continuación.