Je pense qu'un algorithme impliquant des heuristiques serait le mieux adapté ici, l'heuristique étant une notion de la «proximité» du but à chaque étape et du nœud qui vous rapproche du but. Sans cela, je pense que nous aurions besoin d'exécuter un algorithme exponentiel dans le pire des cas (ce qui serait lorsque l'objectif ne peut être atteint en utilisant seulement n nœuds.) Dans ce cas, nous examinerons tous les chemins qui utilisent n nœuds avant de conclure que le problème ne peut pas être résolu). Voici un exemple d'utilisation d'un algorithme non heuristique: Exécuter Dijkstra de manière régulière en sélectionnant le nœud avec un risque min. En cours de route, gardez une trace du nombre de nœuds que vous avez visités. Si le nombre de nœuds dépasse n, abandonnez votre itinéraire actuel et revenez en arrière sur un nœud précédent et utilisez le nœud présentant le risque le plus faible suivant. Naturellement, vous ne pouvez pas faire marche arrière d'un seul niveau au-dessus de n, car si le but était au niveau suivant, il aurait été choisi. Par conséquent, vous revenez au niveau n-2 et continuez. Cela aussi sera exponentiel car il n'y a pas de véritable moyen de déterminer la non-existence sans vérifier tous les chemins.
Il se pourrait aussi qu'il me manque quelque chose.