bonsoir à tous,
je voudrais implémenter un programme qui permet d'avoir un cycle hamiltonien de poids minimum en se basant sur l'algorithme du plus proche voisin dont voici le code:
la table parcours est censée contenir les sommets par lesquels passe le cycle hors que lors de l'exécution il ne rempli que le premier sommet, je ne sais pas ou est l'erreur.
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 #include<stdio.h> #include<stdlib.h> #include<math.h> #include<time.h> int main(){ #define NBSOMMETS 6 printf("coucou\n"); int f,g; int T[NBSOMMETS][NBSOMMETS]= {0,5,8,4,3,2,5,0,4,2,1,3,8,4,0,7,5,4,4,2,7,0,9,8,3,1,5,9,0,4,2,3,4,8,4,0}; for (f=0;f<NBSOMMETS;f++){ for(g=0;g<NBSOMMETS;g++){ printf(" %d\t", T[f][g]); } printf("\n"); } int c; int w,x,y,dist,tmp,z; int min,i,j,l,m,nb,h,a; #define true 1 #define false 0 typedef int bool; bool cycle; int visite[NBSOMMETS]; int parcours[NBSOMMETS]; for(a=0;a<NBSOMMETS;a++){ parcours[a]=999; } for(j=0;j<NBSOMMETS;j++) { visite[j]=0; } /* Initialisation du generateur aleatoire */ i = rand()%(NBSOMMETS); visite[i]=1; parcours[0]=i; int s,q,max; max=0; for(s=0;s<NBSOMMETS;s++){ for(q=0;q<NBSOMMETS;q++){ if (T[s][q]>max){ max=T[s][q];} } } min=max; h=0;dist=0; m=0; while(!cycle){ for (l=0;l<NBSOMMETS;l++) { if (T[i][l]!=0){if (T[i][l]<=min) && (visite[l]==0) { min = T[i][l]; if (min==T[i][l]){tmp=l;}}}} visite[tmp]=1; i=tmp; h=h+1; parcours[h]=i; m=0; while(m<NBSOMMETS){ if (visite[m]==1){ nb=nb+1;} m++;} if (nb==NBSOMMETS) {cycle=1;} else {cycle=0;} } for(c=0;c<NBSOMMETS;c++){ printf("le sommet %d", parcours[c]); printf("\n"); } for(w=0;w<NBSOMMETS-1;w++){ x=parcours[w]; y=parcours[w+1]; dist=dist+T[x][y]; } printf("la distance %d", dist); printf("\n"); return 0; }
quelqu'un aurait une solution??
merci.
Partager