Discussion :

[bricecol]

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 ?

[Aleph69]

Bonjour,

en y ayant réfléchi quelques minutes, la meilleure approche qui me vient à l'esprit est de suivre les étapes suivantes :
1. caractériser la solution du problème pour N=1 (facile),
2. caractériser le meilleur point à ajouter au chemin le plus court en N-1 étapes (en s'inspirant de 1)
Cela te donne un premier algorithme itératif naïf en partant de la solution évidente du cas N=0. Ensuite, je me mettrai à réfléchir aux cas d'échec (plus dur) pour améliorer le procédé. Il y a sûrement beaucoup plus malin mais c'est en tous cas je ce que j'aurais sûrement proposé lors de l'entretien en quelques minutes.

[dev_ggy]

Bonsoir à tous,

La question que je me pose, ne serais pas une forme du problème du vendeur itinérant qui n'a de solution que pour une complexité exponentiel.

[Aleph69]

En fait c'est plus proche du problème du voyageur de commerce mais je crois que le but de l'exercice est simplement de voir comment approcher le problème sans connaissances a priori sur le sujet.

[pseudocode]

Ce problème m'a l'air d'un bon candidat pour de la programmation dynamique.

Par exemple en modélisant la "progression" des chemins qui partent du point A:

soit Di[s] = distance minimum en entre A et "s" à la "i" étape.

D0[s] = 0 si "s"=A, et +oo sinon.
D1[s] = Min { D0[t] + distance(t,s) }, pour tout "t"
D2[s] = Min { D1[t] + distance(t,s) }, pour tout "t"
...

Au final la distance la plus courte pour aller de A à B en n étapes est Dn[B].

Pour avoir le chemin, il faut maintenir la liste noeuds traversés (= le "t" choisi à chaque étape).

[DrDarko]

Bonjour,
Je suis amateur mais bon je me lance.

En gros tu traces ta ligne en pointillé après tu prends N points, les plus proche d'un coté de la ligne en pointillé, tu les relies sans retour en arrière. Ça te fait une 1er distance on va dire de base.
Ensuite tu réitère l'opération de l'autre coté de la ligne en pointillé.
Tu compares et tu gardes la plus petite distance, c'est pas forcément la plus petite distance mais je pense que cela s'en rapproche pas mal.

Ensuite tu peux aussi (si tu n'as pas beaucoup de N points à prendre pour relier A et B) faire un brute force avec un ensemble de points réduit. En gros l'ensemble de point que tu prends c'est les N plus proche de la ligne en pointillé d'un coté plus les N points les plus proches de l'autre coté.

[bricecol]

Merci à tous pour vos réponses.

Il semble effectivement que ce problème ne soit pas trivial... du tout. Je dis çà parce que certaines fois, des problèmes d'apparence complexe ne le sont pas...

pseudocode, je ne suis pas sûr d'avoir tout saisi concernant ta démarche. Est-ce celle-ci : "Trouver le point le plus proche de A, a1. Trouver le point le plus proche de a1, a2 etc... Arrivé à N, relier an à B". Si c'est cette démarche (ce que je doute), alors il y a des contre-exemples. Peux-tu m'expliquer un peu plus en détails ta démarche ?

DrDarko, ta solution en effet est simple à mettre en oeuvre et à le mérite je pense également de trouver une "bonne solution". Sûrement pas la meilleur dans tous les cas, mais elle doit être en plus assez rapide (je ne parle pas du brut force).

[pseudocode]

pseudocode, je ne suis pas sûr d'avoir tout saisi concernant ta démarche. Est-ce celle-ci : "Trouver le point le plus proche de A, a1. Trouver le point le plus proche de a1, a2 etc... Arrivé à N, relier an à B". Si c'est cette démarche (ce que je doute), alors il y a des contre-exemples. Peux-tu m'expliquer un peu plus en détails ta démarche ?

Hum... expliquer de la programmation dynamique ca ne va pas être simple.

Si j'arrive à connaitre:
- le plus court chemin en K étapes pour aller de A à P1 --> longueur L(A,P1)
- le plus court chemin en K étapes pour aller de A à P2 --> longueur L(A,P2)
- le plus court chemin en K étapes pour aller de A à P...
- le plus court chemin en K étapes pour aller de A à Pn --> longueur L(A,Pn)

Alors je peux trouver le plus court chemin en "K+1" étapes (une de plus) pour aller de A à B.

Pour cela:
- je calcule L(A,P1) + distance(P1,B)
- je calcule L(A,P2) + distance(P2,B)
- je calcule L(A,P..) + distance(P..,B)
- je calcule L(A,Pn) + distance(P1,B)

Je regarde quel chemin donne la longueur la plus faible. C'est forcément le plus court chemin pour aller de A à B en "K+1" étapes.

[bricecol]

Je vois maintenant
C'est fonctionnel et cela donne bien la plus courte distance entre A et B ! Merci

Après le problème est de savoir s'il vaut mieux parcourir une distance un peu plus grande que la distance optimale et rattraper ce temps perdu sur la recherche du chemin justement, ou prendre le risque de perdre plus de temps à chercher le chemin que de la parcourir