Discussion :

[kultt]

Bonjour,

J'ai un problème que je n'arrive pas à solutionner moi même :

J'ai un tableau contenant des étapes :



A partir de ce tableau je doit créer un programme permettant de trouver le chemin nécessitant le moins d’étape pour faire PARIS > AUXERRE.

Sachant que dans ce tableau il y a 2 chemin possible :

- PARIS > MELUN >SENS > AUXERRE

- PARIS > MONTARGIS > AUXERRE

le deuxième chemin est évidemment la bonne réponse.

J'ai beau réfléchir je ne trouve pas comment réaliser se programme de façon générique, pouvez vous m'aider ?

Merci d'avance.

[Pascaltech]

Bonsoir,

Serais-tu voyageur de commerce ?

[kultt]

Merci pour l'indice !
Je vais pousser ma recherche dans cette direction, je reviens vers vous si je bloque !

[Pascaltech]

Ton problème est moins compliqué que le problème du voyageur de commerce.

Essaies de remplacer les étapes par des distances, elles seront plus facile à gérer, car moins nombreuses.

Tu poses ton problème de deux manières : le chemin le plus court ou le moins d'étapes ?

[kultt]

Je n'ai pas de distance, c'est vraiment le nombre d'étape qui compte.
Le titre est trompeur, désolé !

[dourouc05]

Les deux manières de formuler le problème sont assez équivalentes : si tu cherches le minimum d'étapes, tu considères que chaque ville est distante de l'autre d'une unité.

C'est un problème assez courant avec des graphes. Vois, par exemple, http://lapoire.developpez.com/algorithmique/graphes/, http://tcuvelier.developpez.com/tuto...-donnees/#LVII.

[tbc92]

C'est quoi, l'école ou bien la FAC où on t'a donné cet exercice ?

[kultt]

@dourouc05 : Merci je vais étudier ça tranquillement.

@tbc92 : ni l'un ni l'autre j'ai fait un test technique (dans le cadre d'un recrutement) qui ressemble à ça. Pourquoi cette question ?

[Pascaltech]

Je n'ai pas de distance, c'est vraiment le nombre d'étape qui compte.
Le titre est trompeur, désolé !

Bonjour,

Tu pourrais donner une valeur à chaque ville et comparer le total par chemin.

Soit deux valeur par étape : PARIS = 1, MELUN = 2, total étape = 3

ou

ville de départ en dizaine et ville d'arrivée en unité : PARIS = 10, MELUN = 1, total étape = 11

Ce n'est qu'une idée, je n'ai pas essayé.

[wiwaxia]

Bonjour,

... J'ai un problème que je n'arrive pas à solutionner moi même :
J'ai un tableau contenant des étapes :



A partir de ce tableau je doit créer un programme permettant de trouver le chemin nécessitant le moins d’étape pour faire PARIS > AUXERRE.
Sachant que dans ce tableau il y a 2 chemin possible :

- PARIS > MELUN >SENS > AUXERRE
- PARIS > MONTARGIS > AUXERRE

le deuxième chemin est évidemment la bonne réponse.

J'ai beau réfléchir je ne trouve pas comment réaliser se programme de façon générique, pouvez vous m'aider ?

Ton énoncé indique 5 villes:
1_Paris
2_Melun
3_Sens
4_Montargis
5_Auxerre

et 5 étapes permises:
<1 - 2>, <2 - 3>, <3 - 5>, <1 - 4>, <4 - 5> parmi les (5 *4 / 2) = 10 arêtes possibles pour le graphe envisagé.

Cela peut se consigner dans une matrice d'adjacence d'ordre 5, où l'on trouve a_ij = 1 ou 0 selon que l'étape est ou non autorisée. Si l'on ne tient compte que des étapes, et non des distances, la solution classique consiste donc à dégager le parcours total de somme (S_aij) minimale, mais ne comportant aucun terme nul.

Une autre recherche est encore envisageable, en considérant qu'il y aura au maximum 3 villes intermédiaires: <1 -a - b - c - 5> , donc 4 étapes. Le parcours total ne dépassant pas 4, on peut reprendre l'initialisation de la matrice précédente en posant a_ij = 1 (unité de distance convenue pour chaque étape autorisée), et a_ij = 10 pour les autres, de sorte qu'une simple recherche du minimum de la distance totale éliminera les parcours comportant une étape interdite.

Le (très) petit nombre de villes autorise une énumération complète des parcours, classés selon le nombre de villes intermédiaires: 0 ,1 , 2 ou 3 , ce qui conduit à l'examen des cas:
<1 - 5> : une solution, exclue;
<1 - i - 5>: 3 solutions;
<1 - i - j - 5> : 6 solutions;
<1 - i - j - k - 5> : 6 solutions.

Cela se programme rapidement.

PS: Il est même possible de se ramener à l'unique dernier cas si l'on autorise l'éventuelle identité de deux étapes consécutives:
(1 = i ; i = j ; j = k ; k = 5); la nullité des termes diagonaux (a_ii = 0) s'accordant avec le fait qu'aucune distance n'est parcourue, si l'on ne sort pas de la ville considérée. Mais il faudra en revanche éliminer quelques solutions inutiles, comme <1 - 4 - 4 - 4 - 5> ou <1 - 4 - 4 - 5 - 5> . en les réduisant au parcours le plus simple: <1 - 4 - 5> , comportant le plus petit nombre de déplacements.