Bonjour à tous,

Je me penche depuis quelques jours sur la résolution d'un problème type voyageur de commerce, avec le but suivant. Sur un tracé comme celui affiché ci dessous (identification algorithmique des cases, d'où le fait que les numéros ne soient pas forcément dans un ordre précis, puisque l'algorithme qui numérote est récursif), j'aimerai passer de ma case 'cell21' (haut à droite), vers la case 'cell12' (en bas à gauche), en passant par toutes les cases, dans un ordre le plus court possible. Voir graph :

Dijkstra me permet bien de tracer le chemin le plus court, mais par conséquent ne passe pas par toutes les cases.

Enfin, le voyageur de commerce ne répond pas parfaitement au besoin, puisqu'il autorise les déplacements en diagonale, avec retour au point de départ.

Je souhaiterai donc implémenter un algorithme du type du voyageur de commerce, avec les contraintes suivantes :

- Début et arrivée différents (mais connus)

- Uniquement des déplacements verticaux/horizontaux. De fait, lorsque l'on arrive en cell4 (haut, milieu), je ne peux aller que en cell3, cell5 ou cell20, sans repasser par des cases déjà utilisées (donc à fortiori si je suis en cell4, il ne me reste au maximum que 2 options de sortie, puisque j'y suis arrivé par une).

- Donc un choix possible fini de nouveaux sommets à partir du sommet actuel (en théorie des graphs).

Je n'arrive pas à trouver les variantes des algorithmes connus qui prennent en compte ce type de critère. j'ai essayé en mettant des poids quasi inifis sur mes chemins diagonaux, sans succès. Quelqu'un connaîtrait il un nom d'algorithme qui conviendrait à mon problème s'il vous plait ?

Merci d'avance & belle journée !

-
Edité par Froggyflag! 20 septembre 2022 à 10:12:23

Bonjour,

si tu veux ne pas pouvoir passer d'une cellule (un nœud) à une (un) autre, il suffit de ne pas les relier … ensuite c'est une «classique» recherche de chemin hamiltonien.