QUESTION : Plus court chemin entre différents points

Bonjour,

Je suis sur un terrain vague. Je dois placer au sol 50 points au GPS dont je connais les coordonnées XY. Je souhaiterais marcher le minimum. Je cherche donc le trajet le moins long pour implanter tous les points. Voilà pour le contexte.

Je pars d'un premier point choisi arbitrairement : Est-ce que si pour choisir le point suivant vers lequel me déplacer mon critère de sélection est "Choisir le point le plus proche de ma position", j'obtiens le chemin total le plus court?

J'ai écris un formule sur Excel pour calculer ça, en image sa donne ce résultat (photo)

https://image.noelshack.com/fichiers/2022/15/4/1649965081-courtchemin.png

Est-ce que ça vous parait le chemin le plus court?

C'est pas le chemin le plus court..

Le 14 avril 2022 à 21:40:31 :
C'est pas le chemin le plus court..

J'ai des doutes moi aussi

Sur le plan de l'exercice de la pense, est-ce que en théorie se déplacer vers le point le plus proche à chaque fois devrait être le chemin total le plus court selon toi?

mozartlivret2
MP
CiterBlacklisterAlerte14 avril 2022 à 21:44:43
Demande à Dijkstra

Je sais pas pourquoi t'as effacé ton message. Merci je vais regarder ça. Au départ je pensais que tu parlais d'un forumeur je t'avais jugé sévèrement

Le 14 avril 2022 à 21:48:08 :
mozartlivret2
MP
CiterBlacklisterAlerte14 avril 2022 à 21:44:43
Demande à Dijkstra

Je sais pas pourquoi t'as effacé ton message. Merci je vais regarder ça. Au départ je pensais que tu parlais d'un forumeur je t'avais jugé sévèrement

Pas sûr que ce soit le bon algo

Le 14 avril 2022 à 21:52:27 :

Le 14 avril 2022 à 21:48:08 :
mozartlivret2
MP
CiterBlacklisterAlerte14 avril 2022 à 21:44:43
Demande à Dijkstra

Je sais pas pourquoi t'as effacé ton message. Merci je vais regarder ça. Au départ je pensais que tu parlais d'un forumeur je t'avais jugé sévèrement

Pas sûr que ce soit le bon algo

Oui effectivement j'ai regardé la vidéo de Yvan Monka dessus j'ai pas eu l'impression qu'on fait face au même problème. Mais je connaissais pas c'était intéressant

Ça ressemble à ça
https://doczz.fr/doc/5693029/heuristiques-du-probl%C3%A8me-du-voyageur-de-commerce

Le 14 avril 2022 à 22:10:32 :
Ça ressemble à ça
https://doczz.fr/doc/5693029/heuristiques-du-probl%C3%A8me-du-voyageur-de-commerce

Oui on se rapproche de mon problème. A un détail près que le commerçant cherche à retourner à son point de départ. Moi je cherche à passer une fois seulement sur chaque emplacement.

C'est comme même bien perturbant. J'étais persuadé que la somme des chemin point à point les plus court serait égale au chemin global le plus court.

J'ai essayé de rajouter des contraintes (distance à un point moyen, à la direction des 2 derniers points, prendre en compte la distance séparant les 2 points suivants .... ça rallonge la distance totale. J'ai réussi à trouver un chemin plus court mais c'était intentionnelle j'avais majoré l'importance d'un point il a donc été évité au départ et j'ai réussi à obtenir une distance totale plus courte.