Discussion :

[tagsOf]

Bonjour à tous,

J'implémente en C une heuristique du voyageur de commerce dans laquelle je dois limité la recherche au k villes les plus proches non visités, j'ai tenter une premiere approche , je souhaiterez que vous me disiez ce que vous en pensez, est ce que cela semble réalisable, je n'ai volontairement pas tout implémenté, le code est commenté:

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include <stdio.h>
#include <stdlib.h>
 
#define NB_VILLES 5
 
static int k=3;
static chemin chemin_mini;
 
struct chemin{
  int * chemin;
  int dstance;
};
 
struct parcours{
  int * chemin;
  int niveau;
};
 
typedef struct parcours * parcours;
typedef struct chemin *chemin;
typedef bool * villeVisite;
 
void parcours(parcour p, villeVisite v){ 
 
 if(p->niveau == NB_VILLES){ //Si le parcours est rempli...
   int dp=distanceParcours(p); //... on calcule sa distance
   if(dp < chemin_mini->distance)//si elle est inferieure a la distance du chemin_mini
     {
       chemin_mini->chemin = p->chemin; //on la sauve
       chemin_mini->distance = dp;// et sa distance aussi
     }
   }
 
   else{ //Sinon c'est qu'il est pas rempli
     int * vpp=kVillesPlusProches(p->chemin[niveau], v); // on récupere dans un tableau les k villes les plus proches de la derniere ville
     for(int i=0; i < k; i++){
       villeVisite v_i=coche(v, vpp[i]); //on cochera la ville que l'on viste dans le tableau de booleen
       parcours p_i=ajouterParcours(p, vpp[i]); //on la rajoute en fin de parcours
       parcours(p_i, v_i);// et on lance les appels récursif
       liberer(v_i, p_i); // on les liberera
     }
   }
}
 
 
int main(void){
  int ville_de_depart=0;
  parcours p=parcoursCreer(ville_de_depart, NB_VILLES);
  villeVisite v=villeVisiteCreer(NB_VILLES);
  coche(v,0);
 
  parcours(p,v);
 
  affiche(chemin_mini);
}

[ToTo13]

Bonjour,

en général, pur chaque ville, il suffit de trier les villes voisines en fonction de la distance, puis de ne parcourir que les K plus proches.