Problème de voyage avec les contraintes

Question

Considérer un réseau avec $ N $ nœuds 1 $, ..., n $. Chaque nœud est connecté à chaque nœud via un bord pondéré, où le poids représente la distance.

Vous commencez votre voyage à un nœud donné, disons $1$, et terminez votre voyage à un nœud donné, disons $12$. Votre voyage a $ T $ pas de temps. À pas de temps $ t = 1 $ Vous devez visiter l'un des nœuds $\{1,7,4\}$, au pas du temps $ t = 2 $ vous devez visiter l'un des nœuds $\{7,3,45,9\}$, etc. En d'autres termes, à un pas de temps donné, vous avez un ensemble avec au minimum $1$ Et au maximum $ K leq n $ nœuds. Choisissez les nœuds pour toutes les étapes de temps de sorte que la distance cumulative est minimisée.

Ai-je raison, qu'un tel problème est difficile NP? Donné $ T $ pas de temps et cela au plus $ K $ Les nœuds sont possibles à chaque pas de temps, la complexité serait $ O (k ^ t) $, droit?

Quels algorithmes pourraient être applicables ou utiles pour un tel problème? Dans mon scénario, $ T $ peut être très grand (jusqu'à 20 000) mais $ K $ est plutôt faible (10 en moyenne, au plus 100).

(Éditer) - J'ai rencontré le problème dans un journal d'un voyageur. Par exemple, vous savez qu'un voyageur a commencé son voyage à un endroit. Pour chaque entrée de voyage, outre le texte brut, l'écrivain du titre écrit une date et un nom de localisation.

Le problème est qu'il existe souvent plusieurs coordonnées différentes pour un nom de localisation (c'est-à-dire que plusieurs emplacements existent avec le même nom). Une hypothèse (je pense raisonnable) à laquelle je suis venu, est que le chemin le plus court possible (du début à la fin) devrait approximativement la route parcourue. J'ai un ensemble de données de plusieurs voyageurs avec des journaux intimes et je veux tracer les itinéraires sur une carte (et espérer afficher un itinéraire parcouru à peu près à la manière dont il a été vraiment parcouru).

Je n'ai pas encore trouvé de solution bonne et générale (en plus de calculer la force brute de la distance de chaque itinéraire possible, ce qui peut être impossible car il existe des tonnes d'entrées de journal et tant de noms de localisation ont plusieurs coordonnées possibles).