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