Sujet Précédent Sujet Suivant

Aidez-moi s'il vous plait !!!!!!!!

starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009 - 3 févr. 2009 à 21:50
starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009 - 5 févr. 2009 à 18:19
Salut a tous!

aidez-moi
s'il vous plait  !!





Je
suis un étudiant en mastère, je suis débutant en programmation, en
effet je travaille sur les méthodes d'optimisation en recherche   opérationnelle, plus précisément  les méta-heuristiques.





Dans
ce qui suit mon programme que j'ai écrits en langage C, qui vise à
rechercher une solution qui va être utilisée par la suite comme une
solution initiale (algorithme de greedy). Je vais essayer d'être bref
pour expliquer qu'est ce que je veux faire exactement.





On a des coordonnes des points  qui
sont stockes dans un fichier de type TXT, j'ai calcule la distance
euclidienne pour avoir une matrice, le but maintenant c'est de trouve
une route pour chaque véhicule celle-ci a une capacité limite (Qmax)
qui doit être respecte et une distance a parcourus limitée (Dmax)
aussi. Chaque client est visité une seule fois et par une seule
véhicule.





P.S. : le nombre de voiture est illimitée, l'essentiel c' visite tout les clients





Chaque voiture doit débuter de l'entrepôt (vertex 0) et retourne à l'entrepôt a la fin de son trajet.





Voila mon programme il marche mais les résultats sont faux.





Voici les données:





V0 0.0000 0.0000 0.0





V1 30.0000 0.0000 10.0





V2 29.6306 40.6930 30.0





V3 28.5317 90.2705 30.0





V4 6.7302 13.6197 10.0





V5 24.2705 17.6336 10.0





V6 11.2132 1.2132 30.0





Veuillez copiez ces donnes dans un fichier de type TXT et entrez l'adresse dans la fonction « getting data from txt file »





Le problème se localise dans la fonction greedy_algorithm pour les autres se marche normalement.





Pour ces donnes le résultat doit être 4 routes :





Route [0] : 0-6-0





Route [1] : 0-4-5-1-0





Route [2] : 0-2-0





Route [3] : 0-3-0





Aidez-moi s'il vous plait !! Merci d'avance à ceux qui prendront la peine d'essayer de coder ou de lire le message.


LE PROGRAMME:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/************Global Variables************/
#define vertices 7 // Number of Customers
#define Qmax 30 //Vehicle Capacity
#define Dmax 100 //Maximum Distance Covered by Each Vehicle

struct data
{
    char label[15];
    float x;
    float y;
    float q;
} tab [500];

/************Getting Data from TXT_FILE************/
int get_data ()
{
    FILE *input;
    char s[80];
    int i,n;
   
input = fopen("C:\\Users\\User\\Desktop\\TEST_FILE.txt","r"); //
veuillez entrez l'adresse ou se localise le fichier de donnees
    if((input)!= NULL)
        printf("File Opened Successfully\n");
    else
        printf("ERROR OCCURRED...File Failed to be Opened!\n");

    n=0;
    while (fgets(s,80,input))
    {
        sscanf (s,"%s%f%f%f", tab[n].label, &tab[n].x, &tab[n].y, &tab[n].q);
        n++ ;
    }
    for (i= 0 ; i <n ; i++)
        printf ("\n%s %3.4f %3.4f %2.0f", tab[i].label, tab[i].x, tab[i].y, tab[i].q);
    return (n);
}

/*****************dynamic allocation for Matrix **********/
float** allocate(int N, int M)
{
    int i;
    float **A = NULL;

    //we allocate memory for N row, it's row pointer
    A = (float**) malloc( sizeof(float*) * N );
    // if allocation succeed we allocate for M column
    if( A != NULL )
        for( i=0; i<N; i++ )
            A[i] = (float*) malloc( sizeof(float) * M );
    if (A == NULL)
    {
        puts("\nFailure to allocate room for pointers");
        exit(0);
    }

    return A;
}

/*************Deallocate Matrix (Free Memory)*******************/
void deallocate( float **A, int N )
{
    int i;
    //free each row
    for( i=0; i<N; i++ )
        free( A[i] );

    free( A );
}

/**********display a table**********/
void display_table( float *vector, int taille )
{
    int i;

    for( i=0; i<taille; i++ )
        printf("[%d] %f\t", i, vector[i]);
}

/******* display a matrix *******8*/
void display_matrix( float **A, int N, int M)
{
    int i, j;

    for(i=0; i<N; i++)
    {
        for(j=0; j<M; j++)
            printf(" %f ", A[i][j]);

        printf("\n");
    }
}

/************compute the Euclidean Distance************/
float** euclidian_distance (float *row, float *column, int t)
{
    int i,j;
    float **matrix;
    float xd=0,yd=0;
    matrix = allocate(vertices, vertices);
   
    printf("\n\nThe Matrix of Distance is:\n");
    for(i=0;i<t;i++)
    {
        for(j=0;j<t;j++)
        {
            xd=tab[i].x-tab[j].x;
            yd=tab[i].y-tab[j].y;
            matrix[i][j]=sqrt((xd*xd)+(yd*yd));
        }
    }
    return (matrix);
}

/**************************search value minimum in matrix*****************************/
float search_value(float **mat, int t, int indice)
{
    float MIN=1000;// each time initialize TEMP to 99.9
    int j;

    for(j=1;j<t;j++)
    {
        if((mat[indice][j]<MIN)&&(mat[indice][j]!=0))
        MIN=mat[indice][j]; // assign the value to TEMP
    }

    return (MIN);
}

/**************************search its indice in matrix*****************************/
int search_indice(float **mat, int t, int indice)
{
    float MIN=1000;// initialize MIN each time
    int j,y;

    for(j=1;j<t;j++)
    {
        if((mat[indice][j]<MIN)&&(mat[indice][j]!=0))
        {
            MIN=mat[indice][j]; // assign the value to MIN
            y=j;
        }
    }
    return (y);
}

/************Construction of Initial Solutions Using Greedy Algorithm************/
void greedy_algo (float **mat, int t )
{
    float **dist, **qte ;
    float MIN;
    int c,i,j,z,k,w,col,x,y;
    float *D,*Q;
    int *indice;
    float *sequence;
    //float **ptr1, *ptr2;
   
    dist = allocate(sizeof (k) , vertices);
    qte = allocate(sizeof (k) , vertices);

    sequence = (float*) malloc (vertices *sizeof (float));
    indice = (int*) malloc (vertices *sizeof(int));

    Q = (float*) malloc(sizeof (k) * sizeof(float) );
    D = (float*) malloc( sizeof (k) * sizeof(float) );

    //initialize table
    for(i=0;i<t;i++)
    {
        Q[i]=0;
        D[i]=0;
    }

    i=0; //initialize row to 0
    j=0;
    for(x=0;x<t;x++)
    {
        for(y=1;y<t;y++)
        {
            while (mat[x][y]!=0)//repeat till the matrix is equal to 0 except column 1
            {
                MIN=search_value(mat,t,i); //printf("\n%f\n",MIN);
                sequence[j]=MIN;
                i=search_indice(mat,t,i); //printf("\n%d\n",i);
                indice[j]=i;
               
                for(z=0;z<t;z++)
                {
                    mat[z][i]=0;// transform the whole column to inorder to avoid return to same point
                }
                j++;
            }
        }
    }
    printf("\n");
    display_table(sequence,t-1);
    puts("\n");
    for(k=0;k<t-1;k++)
        printf("[%d] %d\t",k,indice[k]);

    k=0; //initialize the first route
    col=0;
    w=0;
    for(c=0;c<t-1;c++)
    {
        dist[k][col]=sequence[c]; //printf(" %f\t",dist[k][col]);
        qte[k][col]=tab[indice[c]].q; //printf(" %f\t",qte[k][col]);
       
        Q[k]+=qte[k][col];
        D[k]+=dist[k][col]+mat[indice[c]][0];
       
        if((Q[k]>=Qmax)||(D[k]>=Dmax))
        {
            k++;//goto next road
            col=-1;
            if(c<t-2)
            {
                c++;
                D[k]+=mat[indice[c]][0];//start from the depot
                c--;
            }
        }
        else
            D[k]-=mat[indice[c]][0];
        if (c==t-2)
            D[k]+=mat[indice[c]][0];

        col++;
    }
   
    printf("\n\nmatrice of distance\n");
    display_matrix(dist,k, c);
    printf("Total of Distance of road\n");
    display_table( D, k );
   
    printf("\n\nmatrice of quantity\n");
    display_matrix(qte,k,c);
    printf("Total quantity of road\n");
    display_table( Q, k );

    printf("\n");
    display_matrix(mat,t,t);
}
                 
             
/**************************Principal Program****************************************/
void main (void)
{
    int n;
    FILE *fp;
    float **distance_matrix;
   
    distance_matrix = allocate(vertices, vertices);
   
    fp=fopen("C:\\Users\\Mohamed Anis TRIGUI\\Desktop\\RESULT_FILE_TEST.txt","w");
    n=get_data();
    distance_matrix =euclidian_distance(&tab[100].x, &tab[100].y, vertices);
    display_matrix(distance_matrix,vertices,vertices);
    greedy_algo(distance_matrix, vertices);
}

2 réponses

Réponse 1 / 2
cs_rt15 Messages postés 3874 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 7 novembre 2014 13
5 févr. 2009 à 13:27
Salut,

Autant te le dire tout de suite, je ne vais pas t'aider. Et il y a des chances pour que personne ne t'aide.

Pourquoi ?
1) Il faut apprendre l'algo de greedy et étudier ton code qui fait déjà une certaine taille. C'est long.
2) Aucun intérêt à  première vue sur le plan technique : pas de fonction QuiEstFortRareEtComplexe.
3) Réutilisabilité du code : nulle. On règle ton problème et uniquement ton problème. Personne d'autre n'ayant pas eu exactement le même exo ne pourra réutiliser la solution.
4) Intérêt du code nul. C'est un exo d'étudiant qui a peut de chance d'avoir une quelconque utilité dans la vraie vie.Ca ne va donc rien nous apporter.

Mais j'espère pour toi que je me trompe et qu'un membre va s'intéresser à ton problème.

Dans le cas inverse, il va falloire que tu te démerde tout seul.

Et bin en fait non, tu n'es pas tout seul.

Tu as un débogueur. Si tu n'en as pas tu peux en avoir. Si tu ne peux pas en avoir, tu peux faire sans.

Ton problème est un bug fonctionnel. Il faut que tu compares le fonctionnement de ton code par rapport à l'algo que tu essaies d'appliquer.

Une première méthode consiste à étudier le code en le relisant. Ta fonction greedy_algo est un peu longue. Certains dirait qu'elle est même trop longue. Le fait est que cela nuit gravement au débogage et à la lisibilité de celle-ci. Si tu avais plusieurs sous fonctions, tu pourrais analyser plus facilement si elle renvoie bien ce qu'il faut en fonction des entrée.

Une deuxième méthode consiste à mettre des printf un peu partout pour que le programme décrivent ce qu'il est en train de faire et affichent le contenu des variables. On ajoute et retire en permanence des printf pour se rapprocher du problème.

Une troisième méthode est bien mieux que d'utiliser des printf : c'est d'utiliser un débogueur. Celui-ci permet d'exécuter le code en pas à pas et d'inspecter le contenu des variables sans avoir à écrire des printf de partout.

Divers débogueur plus ou moins bons sont gratuits. Les débogueur sont souvent associés à un IDE. Je vois que tu es sous Windows. A la louche, à l'heure actuelle, du côté des développeurs amateurs, sous Windows, je suppose que 50% utilisent Visual C++, 20% Dev-Cpp, 20% Code::Blocks, 10% le reste.

Sachant que ceux qui u'ilisent Dev-Cpp (Qui n'évolue plus) devraient l'abandonner : il n'a rien de plus que Code::Blocks qui est tout aussi libre et tout aussi gratuit.

Tu peux télécharger Visual C++ 2008 edition express gratuitement, ou Code::Blocks + gcc/MinGW. Les deux ont un débogueur.

Un tuto sur Code::Blocks et son débogueur.
0
Réponse 2 / 2
starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009
5 févr. 2009 à 18:19
Merci, pour ta reponse. en tout cas, en premiere lieu je veux te dire que j'utilise deja visual C++.
secondo, je crois que tu as mal compris le probleme. ce dernier c'est pas a moi seulement comme tu as mentionne, en faite c' un probleme de tournee de vehicule, ce que j'ai fais jusqu'a maintenant c' juste le debut de resolution du probleme, je vais utiliser l'algo de greedy pour generer solution initiale pour le probleme. je vais essaye par la suite d'implementer la methode de recherche tabou pour resoudre ce probleme, si tu as deja connaisance sur les metaheuristiques tu vas bien comprendre l'utilite de ce probleme, en faite il ya pas mal d'auteur qui ont essaye de resoudre ce probleme, je cite ici le pionner l'auteur francais, Taillar. meme les donnes que je vais utiliser dans ce probleme ils sont provient de la bibliotheque ORLIB (biblio de la recherche operationnelle). tu peux visite cette biblio et tu vas trouve les instances  proposes par les auteurs.
En faite merci encore une autre fois pour le temps que tu as pris pour m'ecrire tout ce texte...
En faite, je sais peut etre mon algo c' pas bien j'ai deja dis je suis debutant je suis autodidacte, le programme que tu as vue j'ai depense 1 mois et demi pour ecrire uniquement cette partie
0

Discussions similaires

Besoin d'aide en c # s'il vous plait
haitlhajloutfi -
Whismeril -

6 réponses
repondez s'ils vous plait
monster -
KX -

1 réponse
Une aide s'il cous plait !!!!
marika21 -
capoueidiablo -

3 réponses
Galerie-S'il vous plaît aidez moi...
MissKuroime -
Pylouq -

5 réponses
Signaler Besoin d'aide pour access, s'il vous plait..
julienstagiaire -
julienstagiaire -

4 réponses
Rejoignez-nous