Probleme de recursivite (lie au TSP) :(
Bonjour a tous,
Voila je dois resoudre de la maniere la plus brutale possible (c'est a dire en essyant toutes les possibilite) le probleme du TSP (du voyaveur de commece)
Le but etant de trouver le chemin le plus court en passant une et une seule fois par chaque ville !
Donc pour cela, je sais qu'il faut faire du recursif pour reussir a faire cela mais j'arrive pas a le faire :(
Pour mon probleme, je stocke toutes les villes dans un tableau.
J'ai fais les fonction qui me permettent de calculer la distance entre 2 ville.
Voici un bout de mon code :
Le main d'abord
Code:
1
2
|
parcours_Complet (data); // data est une structure donnees (ayant le nombre de ville du tableau et le tableau |
La fonction parcours_Complet :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void parcours_Complet(donnees d)
{
// Effectuer l'énumération et l'évaluation de toutes les solutions (toutes les permutations possibles) et de choisir la meilleure
float dist_totale=0.0;
int i=0;
printf("nombre de noeud %d\n",d.nb_noeuds);
dist_totale = parcours_Complet_Rec(d,1); // d est les donnees et un est le numero du noeud que je suis entrain de traiter
printf("\n\tParcours Complet :\n");
printf("\t Distance Totale : %10.2f\n",dist_totale);
} |
Et la je sais pas comment implemente ma fonction parcours_Complet_Rec( .. ) pour reussir correctement a faire mes appel recursif (je ne sait pas comment ecrire la condition d'arret deja :()
Bref, je suis totalement dans le flou :(
Si quelqu'un pouvais m'aider je lui en serai reconnaissant !
merci d'avance
Ou si vous avez un liens ou il donne un algo simple de resolution du probleme du voyageur de commerce ? je suis aussi preneur
