Meilleur itinéraire

Voir le sujet précédent Voir le sujet suivant Aller en bas

Meilleur itinéraire

Message  stallaf le Jeu 27 Nov 2008 - 18:31

Bonjour à ED et bonjour à tous,

Je sèche sur un exercice du type "voyageur de commerce". Je vous averti, l'énoncé est long (mon code aussi...). Cela dépasse la capacité d'un topic. Je suis donc contraint de poster ici l'énoncé et le code dans le topic suivant. C'est parti.

"Le but de cet exercice est la recherche de l'itinéraire optimal permettant de joindre deux villes. Lors d'un exercice précédent on a défini la manière de stocker en mémoire une liste de villes, ainsi que les chemins permettant de les relier entre elles.
L' objectif recherché est d'entrer deux villes quelconques dans la liste des villes disponibles et de déterminer le chemin le plus court reliant ces deux villes en indiquant la distance totale à parcourir ainsi que la liste des villes traversées.
Le principe est une recherche arborescente dans le réseau défini en se déplaçant de ville en ville depuis la ville de départ en essayant tous les chemins possibles partant de chaque ville.
Lorsqu'on atteint la ville d'arrivée, on teste si la distance totale parcourue est meilleure que celle précédemment obtenue.On note au fur et à mesure la liste des villes traversées afin de ne jamais passer deux fois par la même étape. La recherche s'arrête lorsque tous les chemins partant du départ ont été explorés.

On considère une liste de villes (Paris, Arras, Reims, Dijon et Metz) reliées entre elles par un réseau d'autoroutes.
L'étape préliminaire consiste donc à mémoriser l'ensemble de ce réseau selon la méthode prévue à l'exercice précédent (tableau pour la liste des villes et matrice de variables structurées pour la liste des chemins). On partira donc des données suivantes :

0
0PARIS
1ARRAS
2 REIMS
3DIJON
4METZ

0 1 2 3
0 1 170 2 140 3 315 -1 0
10 170 4 345 2 160 -1 0
20 140 1 160 4 175 -1 0
3 0 315 4 235 -1 0 -1 0
4 1 345 2 175 3 235 -1 0

Outre ces données on utilise une nouvelle structure à deux éléments : l'itinéraire. Chaque variable du type itinéraire contient deux nombres : un numéro de ville et le numéro d'un des chemins partant de cette ville.
Chaque variable itinéraire permet donc d'accéder à une des cases du tableau chemin (définir le type itinéraire comme DITI).
On se sert de ce tableau comme d'une pile dont la base est la ville de départ. On empile dans le tableau les villes traversées au fur et à mesure qu'on s'éloigne de la ville de départ, et on dépile lorsqu'on recule pour essayer un autre chemin.

La position de la ville courante dans le tableau est repérée par un pointeur FITI.
Pour déterminer le parcours optimal on utilise deux variables : un entier contenant la longueur optimale courante et un tableau d'entiers contenant la liste des numéros de villes composant le parcours optimal courant. Le nombre d'éléments de ce tableau devant être mémorisé.
Voyons maintenant une partie du déroulement de l'algorithme de recherche de l'itinéraire optimal entre Paris et Metz. On notera pour chaque phase les valeurs du tableau itinéraire et du pointeur.

1ère phase : Initialisation
On met dans la première case de DITI le numéro de la ville de départ (Paris = 0) et le numéro du premier chemin à essayer (0).
On met dans long_opti une valeur importante pour que le premier itinéraire trouvé soit considéré comme optimal.

numville 0 - - - - long_iti = 0
numsuiv 0 - - - -
FITI
DITI

2ème phase : boucle effectuée jusqu'à la fin de la recherche
La ville courante est Paris (0) : On met en FITI + 1 le numéro de ville pointé par chemin[0][0]

numville 0 1 - - - long_iti = 0
numsuiv 0 0 - - -
FITI FITI + 1

Le numéro envisagé (1) est différent de -1. Il indique donc une ville existante. On teste si cette ville n'est pas déjà présente dans le tableau DITI. Ce n'est pas le cas on incrémente FITI => la nouvelle ville courante devient Arras et long_iti est incrémenté de 170 kms.

numville 0 1 - - - long_iti = 170
numsuiv 0 0 - - -
DITI FITI + 1

La ville courante est Arras (1) : On met en FITI + 1 le numéro de ville pointé par chemin[1][0]

numville 0 1 0 - - long_iti = 170
numsuiv 0 0 0 - -
DITI FITI FITI + 1

Le numéro envisagé (0) existe déjà dans DITI. On l'ignore, on incrémente FITI => numsuiv pour essayer le prochain chemin partant d'Arras.

numville 0 1 4 - - long_iti = 170
numsuiv 0 1 0 - -
DITI FITI FITI + 1

La ville de Metz n'a pas été encore traversée, elle devient ville courante.

numville 0 1 4 - - long_iti = 515
numsuiv 0 1 0 - -
DITI FITI FITI + 1

La ville atteinte est la ville d'arrivée.On compare les distances et long_opti prend la nouvelle valeur 515 et on recopie dans le tableau optimal[] la liste des villes parcourues.
La recherche ne peut aller plus loin : on décrémente donc FITI pour reculer à la ville précédente et envisgaer le prochain chemin partant d'Arras, long_iti est également décrémenté.

numville 0 1 - - long_iti = 170
numsuiv 0 2 - -
DITI FITI

Le prochain chemin partant d'Arras est Reims

numville 0 1 2 - - long_iti = 170
numsuiv 0 2 0 - -
DITI FITI FITI + 1

La recherche continue à partir de Reims...
Reportons-nous à la dernière étape, celle où la boucle s'arrête.

numville 0 -1 - - long_iti = 0
numsuiv 3 0 - -
FITI
DITI

Après avoir successivement envisagé les chemins 0, 1, 2 partant de Paris, on envisga le chemin trois. Celui-ci indique -1, on décrémente donc FITI et on obtient :

numville 0 -1 - -
numsuiv 3 0 - -
FITI DITI

FIN."

Je suis bloqué à la fin de la première phase de recherche après l'affichage du tableau optimal[].
Je suis sous Windows et Dev C++ (je sais c'est mal ) bounce
Merci.

stallaf

Messages : 4
Date d'inscription : 24/11/2008
Age : 54
Localisation : Gard

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Meilleur itinéraire

Message  -ed- le Ven 28 Nov 2008 - 3:39

stallaf a écrit:Bonjour à ED et bonjour à tous,

Je sèche sur un exercice du type "voyageur de commerce". Je vous averti, l'énoncé est long (mon code aussi...). Cela dépasse la capacité d'un topic. Je suis donc contraint de poster ici l'énoncé et le code dans le topic suivant. C'est parti.
C'est un exercice d'algorithmique. Je pourrais t'aider pour le codage si tu as une analyse claire (algorithme, pseudo-code), mais pas sur l'algo lui même ni sur le choix des structures de donnnées à utiliser. Pas dans mes compétences, désolé. Je connais mes limites !

Je suis bloqué à la fin de la première phase de recherche après l'affichage du tableau optimal[].
Je suppose que tu as eu un cours sur le graphes, l'algo de Dijkstra etc.... Si c'est ça le problème, voir sur le forum Algorithmes de Développez

-ed-
Admin
Admin

Messages : 289
Date d'inscription : 26/05/2008
Age : 60
Localisation : Paris 6eme arrondissement (75, France)

Voir le profil de l'utilisateur http://bien-programmer.fr

Revenir en haut Aller en bas

Re: Meilleur itinéraire

Message  stallaf le Ven 28 Nov 2008 - 11:54

Exclamation
Pour faciliter la lecture de mon sujet (hélas coupé en deux) mes réponses sont dans ce topic. qui affiche le source correspondant.
Merci.

stallaf

Messages : 4
Date d'inscription : 24/11/2008
Age : 54
Localisation : Gard

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Meilleur itinéraire

Message  Contenu sponsorisé Aujourd'hui à 21:19


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum