Bonjour à tous.
Un recruteur m'a posé le problème suivant : Trouver le chemin le plus court entre deux points en passant par N points "étapes". Il m'a posé ce problème via Skype avec une feuille de papier devant sa webcam... Il m'a demandé comment faire sachant que lui ne connaissait pas les algorithmes existants sur le sujet (sous-entendu "trouve moi une solution fiable maintenant sans Dijkstra ou autre" ;p).
Je devais donc me mettre à la place de quelqu'un sans aucune documentation. Comment partir sur ce problème correctement ! Je ne vous demande pas un algorithme concret et fonctionnel mais plutôt comment vous auriez attaqué ce problème en partant de rien ?
Déjà, je vais poser le problème que j'appuie avec ce schéma d'exemple :
On doit relier le point A et le point B en passant ici par 4 points étapes. Le chemin retenu doit être le plus court et bien sûr on imagine qu'il peut y avoir énormément de points (on évitera les algorithmes trop gourmands et surtout celui qui teste toutes les possibilités...). Mon schéma ne le montre pas mais il peut très bien y avoir des points avant A (sur l'axe X) et après B également...
Voici comment j'ai répondu :
J'ai commencé à poser la ligne en pointillée entre A et B qui est le chemin le plus court entre A et B et j'ai d'abord supposé qu'il faille chercher les 4 points les plus proches de cette ligne pour trouver ma réponse (chemin rose). Cependant, prenons le cas d'un groupe de point serrés (à définir plus précisément mais regardez l'exemple). J'ai ainsi créé un contre-exemple à ma première hypothèse : Un chemin bleu plus court que le rose... J'ai ensuite supposé qu'il faille utiliser un mécanisme pour détecter ces groupements. Avec des cercles pourquoi pas ?
Là je me suis arrêté et j'ai dis qu'en partant de rien il me faudrait un peu plus de temps que 2min sur Skype (car il faut prouver l'algorithme : Est-il correcte lui-même et est-il efficace dans tous les cas) ! Ce que, pour la petite histoire, le recruteur à trouver intelligent et m'a ensuite demandé en combien de temps je pensais en être capable :p
Maintenant, je veux mener l'exercice jusqu'au bout ! Aidez-moi !
Avez-vous des suggestions ?
Partager