mon programme ne s'arrete pas !

**laureat** · 10/06/2011, 12h05

Bonjour,

J'ai un graphe de n noeuds.
Voici la structure de données que j'ai utilisé:

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
 
typedef struct Vertex Vertex;
struct Vertex
{
   int no;
    double x;
    double y;
    int demand;
 
};
 
/* cette strucutre n'est pas indispensable, mais fourni une aide */
typedef struct GestionVertex GestionVertex;
struct GestionVertex
{
    int nbreVertices;
    Vertex *tableau; /* Ce tableau a pour but de faciliter la recuperation des données lors de l'evaluation  de la tournee */
    double **distanceEntreVertices;
 
};

.
J'ai écris une fonction qui permet de créer les chemins que va emprunter chaque camion pour visiter les noeuds. Le principe du choix du noeud suivant à visiter est : on choisit le noeud le plus proche en terme de distance.
On commence à construire un nouveau chemin lorsque la capacité du camions est atteinte.
Ci-dessous la structure de données de résultat. içi on a déclaré un tableau indCamions qui va recevoir 1 ou 0 chaque fois qu'on visite le noeud. Il est égale à 1 si le noeud est visité 0 sinon.

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
 
//la tournee  ici est un tableau de client à livrer
typedef struct Circuit Circuit;
struct Circuit
{
 
 
   int *tableau;// ordre de passage chez les clients
   double distanceTotal;
};
//Solution note le tableau de tournees
typedef struct Solution Solution;
struct Solution
{
  int *indCamions; //indice camion pour indiquer l indice de la tournee dans le tableau de tournees
  Circuit *tableau; // tableau des  tournees, Tableau[i]: indice de debut de la  tournee i dans le tableau tournee
  int taille;
  double distance;
};

Vous trouverez ci-après mon programme.
Lors de l'exécution, le programme ne s'arrête pas. La valeur affichée sur la console est zéro.
Quelqu'un pourrait m'aider

?
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
Circuit  *creationCircuit (GestionVertex *GestionVertex, double **distanceEntreVertices,int nbreVertices, int capaciteCamion)
{
    Circuit *Circuit = allocationCircuit(Circuit);
    Solution *Sol = allocationSolution(Sol) ;
    GestionVertex->nbreVertices = nbreVertices;
    GestionVertex->tableau = malloc((GestionVertex->nbreVertices)*sizeof(GestionVertex));
    Circuit->tableau = malloc((GestionVertex->nbreVertices)*sizeof(Circuit));
    Sol->indCamions = malloc((GestionVertex->nbreVertices)*sizeof(Solution));
 
 
 
 
    int demandeTot = 0;
    int i;
    int j;
    //initialisation
    for(i = 0; i < (GestionVertex->nbreVertices)-1; i++)
    {
      Circuit->tableau[i] = -1;
    }
    //calcul le nombre de vehicules necessaires
    for(i = 0; i < (GestionVertex->nbreVertices)-1; i++)
    {
        demandeTot += GestionVertex->tableau[i].demand;
    }
    int nbreCamions = demandeTot / capaciteCamion;
    //calcul la taille de la tournee
    int taille =	(GestionVertex->nbreVertices) -1 / nbreCamions;
    //calcul distance maximale
    double distanceMax = 0;
    for(i=0; i <(GestionVertex->nbreVertices); i++)
    {
        for(j=i+1; j<(GestionVertex->nbreVertices); j++)
	{
            if(distanceMax < distanceEntreVertices[i][j])
                distanceMax = distanceEntreVertices[i][j];
 
	}
    }
 
    //creation des routes en prennant a chaque fois le vertex suivant le plus proche
 
    int tmp = 0;
    int vertexDepart  = 0;
    int position = 0;
    int recommence;
    int cCamion;
    // inserer 0 au debut de la route
    recommence == 1;
    Circuit->tableau[0] = vertexDepart ;
    for(i= 0; i < (GestionVertex->nbreVertices)- 1; i++)
    {
        if(i != 0 )
            vertexDepart = Circuit->tableau[i-1];
       recommence == 1;
        while(recommence)
        {
            recommence == 0;
            //recherche du prochain vertex le plus proche est non deja deservi
            tmp =  circuitRechercheVertexPlusProche(GestionVertex, vertexDepart, distanceEntreVertices, Circuit, distanceMax);
 
            for (j=0; j<i; j++)
            {
                if (tmp == Circuit->tableau[j])
                recommence == 1;
            }
     }
     int capaciteTmp;
     capaciteTmp = capaciteCamion - GestionVertex->tableau[tmp].demand;
     if(capaciteTmp >= 0 && position > (taille))
     {
            Sol->indCamions[i] = 1;
            cCamion = capaciteCamion;
            cCamion -= GestionVertex->tableau[tmp].demand;
            position = 0;
	   //if ( i != ((GestionVertex->nbreVertices)-2))
            //Sol.tableau[i+1] = tmp;//augmenter d'une unité le tableau
 
      }
      else
      {
            if(capaciteTmp >= 0)
            {
                cCamion -= GestionVertex->tableau[tmp].demand;
                if(i == ((GestionVertex->nbreVertices)-2))
                {
                    Sol->indCamions[i] = 1;
              }
               else
                    Sol->indCamions[i] = 0;
        }
         else if (capaciteTmp < 0 )
         {
                Sol->indCamions[i-1] = 1;
                vertexDepart = Circuit->tableau[i];
                if (i == ((GestionVertex->nbreVertices)-2))
                {
                    Sol->indCamions[i] = 1;
                }
                else
                {
                    Sol->indCamions[i] = 0;
                }
                cCamion = capaciteCamion;
 
                cCamion -= GestionVertex->tableau[tmp].demand;
                position = 1;
            }
        }
 
		Circuit->tableau[i] = tmp;
		position++;
    }
 
 
}
 
 
/*
* Renvoie le numero du vertex le plus proche de v_depart
*/
int circuitRechercheVertexPlusProche(GestionVertex *GestionVertex,  int vertexDepart, double **distanceEntreVertices,  int *tableauDejaUtilise, int distanceMax)
{
    double distanceMin = 0;
    int continuer;
    int trouve;
    int i;
    int j;
    int nbreVertices = 6;
    int vertexProche = 0;
    GestionVertex = allocationGestionVertex(GestionVertex, nbreVertices);
    GestionVertex->nbreVertices = 6;//ligne ajoute
    continuer == 1;
    trouve == 0;
 
    for (i=1; i < (GestionVertex->nbreVertices); i++)
    {
        continuer == 0;
        for (j=0; j <  (GestionVertex->nbreVertices) - 1; j++)
        {
            if (i == tableauDejaUtilise[j])
                    continuer == 0;
        }
        if ((i!= vertexDepart))
        {
            printf("%d", vertexDepart);
            if(distanceEntreVertices[vertexDepart][i] < distanceMin)
            {
                trouve == 1;
                vertexProche = i;
                distanceMin = distanceEntreVertices[vertexDepart][i] ;
            }
        }
    }
   return vertexProche;
}
/*Affiche la tournee mais ajoute aussi l'affichage de la demande totale de chaque tournee
* ainsi que la capacite des camions disponible*/
void circuitAffichage(GestionVertex *GestionVertex,int capacite, int nbreVertices, int nbreCamions)
{
    Circuit *Circuit;
    Solution *Sol;
    GestionVertex->nbreVertices = nbreVertices;
    GestionVertex->tableau =  malloc((GestionVertex->nbreVertices)*sizeof(GestionVertex));
    Circuit->tableau = malloc((GestionVertex->nbreVertices)*sizeof(Circuit));
    Sol->tableau = malloc((GestionVertex->nbreVertices)*sizeof(Solution));
 
    int i;
 
 
 
    for (i=0; i < (GestionVertex->nbreVertices)-1; i++)
    {
        printf("Circuit.tableau[%i] : %d\n", i, Circuit->tableau[i]);
    }
 
    for(i=0; i < nbreCamions; i++)
    {
        printf("Solution.tableau[%i]: %d\n",i, Sol->tableau[i]);
    }
 
    double demande = 0;
    int circuit = 1;
    int origine = 0;
    int respect;
    respect == 1;
    for(i=0; i < ((GestionVertex->nbreVertices)-1); i++)
    {
        if(Sol-> indCamions[i] == 0 )
        {
            if(demande == 0 )
            {
                origine = i;
            }
            demande += GestionVertex->tableau[i].demand;
        }
        else
        {
            demande += GestionVertex->tableau[i].demand;
            if (demande > capacite)
            {
                respect == 0;
            }
            printf( "Circuit num : %d  de  %d a  %d demande --> %d\n",circuit, origine, i, demande);
            circuit++;
            demande = 0;
        }
    }
    if (!respect )
    {
        printf("Attention -> ici : Non respect de la contrainte demande !\n ");
    }
    else
    {
        printf("Tout va bien ici la contrainte de demande est respectee :-) ! \n" );
    }
 
 
}

**skeud** · 10/06/2011, 13h20

Bon je t'avourais que le code est plutot long pour le comprendre dans son ensemble en peu de temps.

Quand tu dis que ton programme ne s'arrete pas c'est surement qu'il boucle de maniere infini.essaie dans un premier temps de fouiller pour trouver quelle boucle part en cacahuete en mettant des debug dans toutes les boucle, le debug qui aparait tout le temps sera celui de la boucle infini.

Une fois que tu as identifier la boucle, verifie les conditions de sortie en l'affichant sur la sortie standard et tu pourras savoir pourquoi sa cloche

**nico1811** · 10/06/2011, 14h42

Bonjour,

Tu utilises des tests d'égalité (==) au lieu affecter une valeur à tes variables (=).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 while(recommence)
        {
            recommence == 0;
            //recherche du prochain vertex le plus proche est non deja deservi
            tmp =  circuitRechercheVertexPlusProche(GestionVertex, vertexDepart, distanceEntreVertices, Circuit, distanceMax);
 
            for (j=0; j<i; j++)
            {
                if (tmp == Circuit->tableau[j])
                recommence == 1;
            }
     }