Bonjour,
Je voudrais écrire l'algorithme ci-dessous en C:
Ci-dessous mon programme. Pourriez-vous me le corriger?met le noeud zero comme premier noeud à visiter dans Circuit->tableau[0]
ensuite, chercher le noeud qui a la plus grosse demande et qu'on le met dans Circuit->tableau[1]
Après, On recherche le noeud le plus proche que l'on ajoute dans Circuit->tableau[2]. Si le noeud est déjà dans la liste des noeuds visités, on prend le deuxième noeude plus proche,ainsi de suite.
Merci par avance.
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110 typedef struct Noeuds Noeuds ; struct Noeuds { int no; double x; double y; int demand; }; /* cette strucutre n'est pas indispensable, mais fourni une aide */ typedef struct GestionNoeuds GestionNoeuds; struct GestionNoeuds { Noeuds tableau[nbreNoeuds]; /* tableau de Noeuds */ double **distanceEntreVertices; }; struct Circuit { int tableau[nbreNoeuds]; }; typedef struct Circuit Circuit; /** *allocation dynamique de la structure Circuit */ Circuit *allocationCircuit(void) { Circuit *pCircuit; pCircuit = malloc(sizeof *pCircuit); return pCircuit; } /** *Cette fonction permet de chercher le noeud qui a la plus grosse demande */ int chercherIndiceNoeudPlusGrosseDemande(GestionNoeuds *pGestionNoeuds) { int demandMax = 0; int indiceNoeud; int i; for(i=1; i<nbreNoeuds;i++) { if(demandMax < (pGestionNoeuds->tableau[i].demand)) indiceNoeud = i; } return indiceNoeud; }Circuit* recherchePlusProcheVoisin(GestionNoeuds *pGestionNoeuds) { int i,j,k,tmp; int cycle = 0; /* Booléen */ int visite[nbreNoeuds] = {0}; /* visite[i]=1 : */ Circuit *pCircuit; pCircuit= allocationCircuit(); int deuxiemeNoeud; /* Ici, on va constituer une solution. */ /* On initialise */ for (i=0 ; i<nbreNoeuds ; i++) pCircuit->tableau[i] =-1; int ind=2; /* Indice du tableau */ /* Parcours */ int min; /* Minimum */ double **distanceEntreNoeuds = calculDistance(pGestionNoeuds); pCircuit->tableau[0] = 0; deuxiemeNoeud = chercherIndiceNoeudPlusGrosseDemande(pGestionNoeuds); pCircuit->tableau[1] = deuxiemeNoeud; visite[deuxiemeNoeud]=1; while ( !cycle ) { k=1; /* On se place sur le premier sommet non visité */ while ( visite[k] ) k++; min=distanceEntreNoeuds[deuxiemeNoeud-1][k-1]; tmp=k; for ( j=k+1 ; j<=nbreNoeuds ; j++) /* Recherche du plus */ /* proche voisin */ { if (distanceEntreNoeuds[deuxiemeNoeud-1][j-1] < min && !visite[j] ) { min = distanceEntreNoeuds[deuxiemeNoeud-1][j-1]; tmp=j; } } ind++; pCircuit->tableau[ind]=tmp; visite[tmp]=1; for ( i=1 ; i<=nbreNoeuds ; i++ ) /* Calcul du booléen cycle */ { if ( visite[i] ) cycle=1; else { cycle=0; break; } } i=tmp; } ind++; return pCircuit; }
Partager