Bonjour,
SVP j'ai besoin de votre aide dans mon programme qui ne renvoie pas le bon résutat.
Merci par avance.
J'ai une suite des noeuds suivante:
0, 1, 2, 3, 4, 5.
J'ai la demande respectivement sur les noeuds
0, -1, 1, 3, -3, 1
J'ai aussi les distances entre tous les noeuds (la distance est symètrique):
distance(0,0) = 0
distance(0,1) = 4
distance(0,2) = 3
distance(0,3) = 2
distance(0,4) = 5
distance(0,5) = 1
distance(1,0) = 4
distance(1,1) = 0
distance(1,2) = 3
distance(1,3) = 4
distance(1,4) = 5
distance(1,5) = 6
distance(2,0) = 4
distance(2,1) = 1
distance(2,2) = 0
distance(2,3) = 4
distance(2,4) = 5
distance(2,5) = 6
distance(3,0) = 2
distance(3,1) = 3
distance(3,2) = 4
distance(3,3) = 0
distance(3,4) = 5
distance(3,5) = 6
distance(4,0) = 4
distance(4,1) = 0
distance(4,2) = 3
distance(4,3) = 4
distance(4,4) = 0
distance(4,5) = 6
distance(5,0) = 1
distance(5,1) = 4
distance(5,2) = 3
distance(5,3) = 1
distance(5,4) = 5
distance(5,5) = 0
Je cherche à insérer à chaque fois le noeud le plus proche dans la variable tableau et je teste si la charge entre les noeuds précedent et ce noeud est positive ou égale à zero.Si c'est OK(la condition est vrai), je l'insère . Sinon, je cherche un autre noeud plus proche au noeud précédent. Je vérifie ensuite que la condition est vrai et ainsi de suite jusqu'à ce que tous les noeuds sont insérés.
Voici la formule de calcul de la charge:
charge = demande (i-1)+ demande(i).
Voici à quoi ressemble le résultat:
i=0
je mets zero au debut dans mon tableau
tableau[0] = 0
i=1
je cherche le noeud le plus proche par rapport au noeud précedent (le noeud 0):
Quel est le noeud le plus proche à zero?
C'est le noeud 5 car distance(0,5) est la plus petite. La charge entre le noeud precedent (le noeud zero)et ce noeud (neoud 5) est négative. Donc, je ne prends pas.
-->Je vais chercher alors une autre noeud parmi les noeuds restants.
tableau[1] = ?
i=2
Quel est le noeud le plus proche au noeud 0?
on a la distance (0,3) est plus petite car distance(0,5)<distance(0,3). Je vérifie la charge. La charge est positive. Donc, je le prends.
tableau [2]= 3
i=3
quel est le neoud le plus proche au noued 3?
C'est le noeud 1.Car la distance(3,1)est plus la plus petite. Je ne peut pas prendre le neoud 0 ou le noeud 3 car je l'ai dejà dans mon tableau.
Je verifie le test: la charge est >=0? oui car 1+(-1)=0.
Donc, je prends
tableau[3] = 1
et ainsi de suite.
Ci-dessous mon programme. Mon problème c'est dans le cas où le noeud le plus proche sélectionnée ne vérifie pas la condition (la condition est faux).
Je m'explique.
Dans l'exemple ci-dessus à i=1:le noeud le plus proche est 5.
Mais, la condition n'est pas vrai( la charge est négative).
Alors, je dois chercher un autre noeud proche au noeud précédent (noeud zéro)et qui vérifie cette condition.
Mon algorithme me prends toujours le noeud 5.
Je ne vois pas comment corriger ça. Il doit prendre le noeud suivant le plus proche au noeud zero à savoir le neoud 3
.
Merci par avance de vos aides.
Voici mon code.
Code: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 construire la Circuit->tableau */ Circuit* creationCircuit(int noeudDepart, double **distanceEntreNoeuds, Noeuds tableau[nbreNoeuds] ) { int i; int j; Circuit *pCircuit; pCircuit= allocationCircuit(); /* Ici, on va constituer une solution. */ /* On initialise */ for (i=0 ; i<nbreNoeuds ; i++) pCircuit->tableau[i] = i; int noeudDebut = 0; int temp; int charge = 0; pCircuit->tableau[0] = noeudDebut; charge += tableau[0].demand; printf("\ncharge:%d\n", charge); for(j=1;j<nbreNoeuds;j++) { i=0; temp = chercherNoeudPlusProche(distanceEntreNoeuds, pCircuit->tableau[j-1]); capacite -=tableau[temp].demand; charge += tableau[temp].demand; printf("\n charge: %d\n", charge); printf("temp: %d\n",temp); if(charge>=0) { //insérer l'élement dans le tableau pCircuit->tableau[j]= temp; printf("supprimer temp\n"); memmove (tableau +temp, tableau + temp+1, sizeof (int) * nbreNoeuds); } else { i=1; } i++; } return pCircuit; } /* *Renvoie l'indice du noeud le plus proche */ int chercherNoeudPlusProche(double **distanceEntreNoeuds, int noeudDebut) { double distanceMin = 1000; int noeudProche = 0; int i; for (i=1; i < nbreNoeuds; i++) { if ( (i != noeudDebut) && distanceEntreNoeuds[noeudDebut][i] < distanceMin) { distanceMin = distanceEntreNoeuds[noeudDebut][i] ; noeudProche = i; } } return noeudProche; }
-----
Envoyé par celine2 
Re : langage C: problème avec mon programme
.
Re : langage C: problème avec mon programme
. Je veux savoir la solution