Sujet Précédent Sujet Suivant

Algorithme de greedy

starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009 - 2 févr. 2009 à 18:18
starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009 - 2 févr. 2009 à 18:21

<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="ProgId" content="Word.Document" />
<meta name="Generator" content="Microsoft Word 12" />
<meta name="Originator" content="Microsoft Word 12" />
<link rel="File-List" href="file:///C:%5CUsers%5CMOHAME%7E1%5CAppData%5CLocal%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_filelist.xml" />
<link rel="themeData" href="file:///C:%5CUsers%5CMOHAME%7E1%5CAppData%5CLocal%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_themedata.thmx" />
<link rel="colorSchemeMapping" href="file:///C:%5CUsers%5CMOHAME%7E1%5CAppData%5CLocal%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_colorschememapping.xml" />


<style>

</style>


Salut a tous!

S’il vous plait aidez-moi !!

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 limité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 [0] :
0-4-5-1-0

Route [0] :
0-2-0

Route [0] :
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);
}

A voir également:

Algorithme de greedy
Algorithme de prim - Forum C / C++ / C++.NET
Code maroc algorithme - Forum C
Algorithme minmax - Forum VB.NET
Algorithme loto excel gratuit ✓ - Forum Visual Basic
Algorithme de horner - Forum C / C++ / C++.NET

1 réponse

Réponse 1 / 1

starbluesky Messages postés 7 Date d'inscription mardi 27 janvier 2009 Statut Membre Dernière intervention 18 février 2009
2 févr. 2009 à 18:21

excuser moi pour la faute
les resultats doivent etre
Route [0] : 0-6-0

// 1er route

Route [1] : 0-4-5-1-0 // 2eme route

Route [2] : 0-2-0 // 3eme route

Route [3] : 0-3-0 // 4eme route
4 routes en totales

Discussions similaires

Algorithme de vérification RIB (24 chiffres / maroc)

Cherche algorithme Affectations de groupes dans des salles

recherche d'un code ou de l'algorithme

conversion algorithme en code vba

[VBA / macro excel] remise à vide de cellules à chaque début de mois.

Rejoignez-nous