Discussion :

[piff62]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[nicolas581]

Un exemple d'algorithme :

On code un solution de la forme
Sol : (k, [i1, ..., ik], c) où
- k = nb de ville,
- [i1,...ik] = chemin
- c = cout

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
TSP_naif(S_partielle, Meilleur cout) 
debut
  S_partielle = (k, [i1, ... , ik], w);
  Meilleur_cout = (n,[im1, ..., imn], m);
  si k=n alors
    cout <- w + w[ik, i1]
    si cout < m alors 
      Meilleur cout <- (k, [i1, ..., ik], cout)
     fsi
  sinon
       /* Si (w < meilleur_cout) alors */ 
       /* permet d'elaguer un peu l'arbre de recherche, aucune utilité de continuer si la solution partielle est deja superieure à la meilleure solution connue */
       pour j \not \in [i1, ..., ik] faire
         /* Amélioration :  comment choisir j, certains choix sont plus judicieux */
         Ns = (k+1, [i1, ..., ik, ij], w+w[ik, ij]) ;
         Tsp_naif(Ns, Meilleur_cout) ;
       fpour
     fsi
fin

Plus qu'à transcrire dans ton langage de programmation préféré, ce qui n'est que du sucre syntaxique comme dirait Philou.

PS : pourquoi mettre du C dans un forum d'algorithmique : bien séparer le fond (algo) de la forme (un langage) dans ta tête.

[piff62]

Merci nicolas581,
Je regarde ca des que j'ai un peu de temps ..
et je te tiens au courant car la je dois reviser une salete de DS de maths pour demain ..
@ bientot

[piff62]

Desole de t"embeter a nouveau mais j'ai une petite question !

S_partielle = (k, [i1, ... , ik], w);
Meilleur_cout = (n,[im1, ..., imn], m);
si k=n alors

Je veux bien .. mais j'aimerai savoir comment tu choisi les valuers de k et de n ?
k je pense bien que c'est le nombre de ville a visiter ..
mais n ? comment le choisir ce fameux n ?
Et comment puis je stocke les informations de S_partielle ? sous forme de tableau ?

Merci de tes reponses!
@ bientot .. surement

[nicolas581]

k est le nombre de villes de ta solution partielle donc à l'initialisation 1, il faut bien partir d'un ville pour que le voyageur fasse sa tournée.
n est le nombre de villes à visiter.
Le chemin courant est stocké sous forme de tableau.

Concernant l'implémentation :
Utilisation de tableau (au sens C) car si tu utilises des listes (càd avec chaînage, au sens C aie aie le temps des suppressions / ajouts) même si ça ne veut rien dire d'un point de vue algorithmique car une liste peut être représentée sous forme de tableau et pas forcemment sous forme de chaînage mais ici je parle du C.
Tu peux très bien avoir une bibliothèque C de liste qui a deux implémentations (sous forme de void * tab, ou sous forme void *valeur, struct element *suivant).
Tu as la même interface pour les deux "classes" mais une implémentation différente.

J'espère avoir été clair.

[piff62]

Merci,
je jete un coup d'oeil manan a tous ceci
Si bien oui, j'implemente avec un tableau donc aucun souci pour ca
Encore merci !

[piff62]

Desole de t'embeter a nouveau nicolas581,
Mais j'ai du mal a retranscrire ca en C ..

TSP_naif(S_partielle, Meilleur cout)

S_partielle et Meilleur_cout .. doivent etre des float representant la longeur ?
Des tableau representant le chemin ?

Enfin bref, je suis perdu ..
Tu aurai pas l'exemple que tu m'as donne code en C ?
Je suis desole de t'importuner !
Piff62

[nicolas581]

J'ai du mal a retranscrire ca en C ..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
TSP_naif(S_partielle, Meilleur cout)

S_partielle et Meilleur_cout .. doivent etre des float representant la longeur ?

Comme tu veux, selon l'énoncé comme c'est un exercice, je ne le connais pas. J'espère que tu te rends bien compte que le choix de float ou de int c'est vraiment secondaire.

Des tableau representant le chemin ?
Comme dit deux posts plus haut : Le chemin courant est stocké sous forme de tableau mais
si tu veux utiliser autre chose tu peux.

Tu n'aurais pas l'exemple que tu m'as donné code en C ?