Renaud Heitz

S'il y a toujours un mur, je retourne à droite.

Et souvent, on finit par faire des robots qui tournent en rond.

Donc il faut aller vers des vrais algos, où on fait une vraie modélisation de la carte, des endroits où ça passe, des endroits où ça ne passe pas, et on va chercher, donc on le modélise, comme tu l'as dit, sous la forme d'un graphe.

Donc un graphe, c'est des nœuds, des endroits où je peux être, et des arrêtes, c'est les endroits où je peux aller à partir de cette position-là.

Et de là, on va pouvoir itérer.

Et donc là, il y a plusieurs façons de le faire.

Le premier mathématicien qui a proposé une solution, il s'appelle Dichtra.

Dichtra, donc c'est facile.

On fait un rond, donc on part de l'endroit où je suis, je vais explorer ceux qui sont autour, puis ceux qui sont autour de ceux qui sont autour.

Et donc en fait, on va avoir une sorte de rond où je vais partir de l'endroit où je suis, je regarde tous les chemins possibles jusqu'à ce que mon rond, il touche ma destination.

Et là, je dis, ah, j'ai trouvé un chemin qui va à ma destination.

C'est bien, mais c'est long.

C'est-à-dire que si je veux trouver le chemin qui m'emmène, disons, aller à Marseille, je vais aussi trouver le chemin qui m'emmène à Berlin, parce que les deux sont à 1000 km.

Donc j'aurais trouvé tous les chemins amenant dans toutes les villes allant de Paris à toutes les villes à moins de 1000 km.

Il y a beaucoup de calculs pour rien, quoi.

donc il y en a qui vont permettre d'aller plus vite sans trouver forcément la meilleure solution mathématiquement et il y en a qui vont garantir et qui vont avoir des garanties mathématiques tout en allant beaucoup plus vite donc là ça va être en gros on va dire on va progresser non plus en forme de rond mais plutôt en forme d'ellipse en disant je sais que le chemin restant il fait au moins la distance à vol d'oiseau

Donc à un moment, si j'ai un chemin qui se rapproche, il vaut mieux l'explorer que le chemin qui m'éloigne.

Et du coup, au lieu de progresser en rond, on va progresser en forme d'ellipse dans la direction qu'on vise.

Donc il y a deux choses, il y en a un, c'est le chemin le plus court en kilomètres, ça tout le monde sait le trouver, c'est pas très dur, maintenant il y a des algos qui permettent de garantir, oui c'est sûr.

Après la deuxième difficulté, c'est qu'on va avoir parfois des boucles où en fonction de l'heure à laquelle je passe, j'aurai pas le même trafic, et donc j'aurai pas le même temps de parcours.