programmer un algorithme

[simloun]

Bonjour tout le monde
je travaille sur un projet, qui utilise pas mal de programmation basique, je ne suis pas spécialiste en la matière, donc je tire une grosse sonnette d'alarme.
Le problème de VRP (vehicle routing problem) consiste à déterminer en minimisant le coût, un ensemble de tournées, pour un nombre limité de véhicules, commençant et finissant à un dépôt
L’étude de tout ça se fait sous plusieurs étapes. La première c’est qu’on doit prendre un des algortihmes proposé par un des mathématitiens, j’ai choisis un qui s’appelle “CLARK AND WRIGHT”. Donc il faut programmer l’algorithme et l’appliquer sur des données connues de villes et de demande. Ces données(instances) sont dans des fichers. Il faut donc écrire tout d’abord une fonction en C ou C++ qui lit ces données à partir d’un fichier. J’ai proposé la fonction suivante mais que j’ai du mal à achever parce qu’il me manque quelques fonctions que j’arrive pas à introduire :

/LECTURE D'UN FICHIER
//DONNES UTILES pour la fonction:
ville **tabVille;

//il me faut une class ville définie dans un autre fichier, champs utiles: coordonnées, demande

//une fonction qui calcule la distance euclidienne entre deux villes:
d_ij = sqrt(pow(i->x()-j->x(),2)+pow(i->y()-j->y(),2))
int nbVille;
double CAPACITE;
// inclure les librairies utiles

//fonction qui lit le fichier nomFichier.vrp, où nomFichier est le paramètre
void lireFichier(char *nomFichier) {
char *nomFichierComplet = new char [200];
sprintf(nomFichierComplet,"%s. vrp",nomFichier);
FILE *f = fopen(nomFichierComplet,"r");
if (f == NULL) {
cout << "Impossible de lire le fichier " << nomFichierComplet << endl;
exit(1);
}
CAPACITE = -1;
.
.
.
.
Je sais pas si ce debut de programme est juste et aussi j’arrive à introduire tout ce qui est en gras !!
Lerci beauuuucoup for help

[argusazure]

Je n'ai lu qu'en diagonale, mais c'est quoi le problème. Essai de structurer ton problème en classe si tu veux faire de la programation objet. Ca permet de faire des choses plus claire. Tu fais ta classe ville (nom, coordonnées...) , ta classe monde (qui contient la liste de tes villes les la fonction de lecture du fichier qui contient les villes)
Pour lire dans un fichier texte en c, c'est un truc comme ça:
[code]
FILE *fic;
fic=fopen("nomFichier.txt","rt ");
if (fic==NULL)
{
std::cerr << "error ..."<< std::endl;
return 1;
}
char pszVille[TAILLE_VILLE];
fscanf("ville %s",pszVille);
fclose(fic);

[Gre]

simloun, il y a une balise qui permet de mettre en forme votre code. C'est la balise CODE (le bouton avec un dièse)

Ainsi

FILE *fic;
char pszVille[TAILLE_VILLE];

fic=fopen("nomFichier.txt","rt");
if (fic==NULL)
{
    std::cerr << "error ..."<< std::endl;
    return 1;
}

fscanf("ville %s",pszVille);
fclose(fic);

Bon sinon... on évite les déclarations de variables dans le cours du corps de programme. Ça nuit sérieusement à la lecture. Parfois c'est important de le faire. Mais là ce n'est vraiment pas le cas. Les exit dans les fonctions c'est pas forcément une bonne idée non plus. C'est souvent un moyen mis en œuvre quand on a pas le contrôle de son programme et qu'on en a qu'une vu superficielle.

Simloun > tu es parti pour faire du C. Si tu veux des classes pourquoi ne pas partir en C++ ? Les bibliothèques (plutôt que les librairies qui est un anglicisme) se déclarent au début. Comme le dit argusazure, où sont tes questions ?

[simloun]

salut
mon probleme est surtout en implementaion, j'arrive pas à mettre les declarations en place, on m'a passé une indication d'un code mais il est bourré d'erreur et je suis incapable de corriger. Je suis PERDU; le code complet est :

//LECTURE D'UN FICHIER
//DONNES UTILES pour la fonction:
ville **tabVille;
  //class ville définie dans un autre fichier, champs utiles: coordonnées,
demande
  //besoin d'une fonction qui calcule la distance euclidienne entre deux villes:
d_ij =  sqrt(pow(i->x()-j->x(),2)+pow(i->y()-j->y(),2))
int nbVille;
double CAPACITE;
//et penser à inclure les librairies utiles

//fonction qui lit le fichier nomFichier.vrp, où nomFichier est le paramètre (pe
A-n65-k9) 
void lireFichier(char *nomFichier) {
  char *nomFichierComplet = new char [200];
  sprintf(nomFichierComplet,"%s.vrp",nomFichier);
  FILE *f = fopen(nomFichierComplet,"r");
  if (f == NULL) {
    cout << "Impossible de lire le fichier " << nomFichierComplet << endl;
    exit(1);
  }
  CAPACITE = -1;
  nbVille = -1;
  char *lineBuf = new char [500];
  while (fgets(lineBuf, 500, f)) {
    if (strncmp(lineBuf, "DIMENSION",strlen("DIMENSION")) == 0) {
      if (sscanf(lineBuf, "DIMENSION : %d", &nbVille) != 1) {
        cerr << "Erreur lors de la lecture de la DIMENSION" << endl;
        exit(1);
      }
    }
    if (strncmp(lineBuf, "CAPACITY", strlen("CAPACITY")) == 0) {
      if (sscanf(lineBuf, "CAPACITY : %lf", &CAPACITE) != 1) {
        cerr << "Erreur lors de la lecture de CAPACITY" << endl;
        exit(1);
      }
    }
    if (strncmp(lineBuf, "NODE_COORD_SECTION", 
                strlen("NODE_COORD_SECTION")) == 0) {
      break;
    }
  }
  if (CAPACITE == -1 || nbVille == -1) {
    cout << "Erreur lors de la lecture : pas de dimension ou de capacité
trouvée" << endl;
    exit(1);
  }
  tabVille = new (ville *) [nbVille];  //CREATION du tableau tabVille
(ATTENTION, penser à le supprimer à la fin du programme)
  int i = 0;
  int n;
  double x,y;
  while (fgets(lineBuf, 500, f)) {
    if (strncmp(lineBuf, "DEMAND_SECTION",strlen("DEMAND_SECTION")) == 0) {
      break;
    }
    if (sscanf(lineBuf,"%d %lf %lf",&n,&x,&y)== 3) 
      if (n > nbVille || n < 1) {
        cerr << "Erreur de lecture des coordonnees : le numero de la ville ";
        cerr << "doit etre compris entre 1 et " << nbVille;
        cerr << " (ville numero " << n << ")";
        cerr << endl;
        exit(1);
      } else if (tabVille[n-1] != NULL) {
        cerr << "Erreur de lecture : la ville " << n;
        cerr << " est definie 2 fois..." << endl;
        exit(1);
      } else {
        tabVille[n-1] = new ville (n,x,y);  //CREATION ville num n de coord
(x,y)
        i++;
      }
  }
  if (i != nbVille) {
    cerr << "Erreur de lecture : " << i << " villes lues et dimension=";
    cerr << nbVille << endl;
    cerr << "Il manque la definition des villes ";
    for (int j=0; j<nbVille; j++)
      if (tabVille[j] == NULL) cerr << j << " ";
    cerr << endl;
    exit(1);
  }
  double d;
  i=0;
  while (fgets(lineBuf, 500, f)) {
    if (strncmp(lineBuf, "DEPOT_SECTION",strlen("DEPOT_SECTION")) == 0) {
      break;
    }
    if (sscanf(lineBuf,"%d %lf",&n,&d)== 2) 
      if (n > nbVille || n < 1) {
        cerr << "Erreur de lecture de la demande : le numero de la ville ";
        cerr << "doit etre compris entre 1 et " << nbVille;
        cerr << " (ville numero " << n << ")";
        cerr << endl;
        exit(1);
      } else if (d < -0.0001) {
        cerr << "Erreur de lecture : la demande de la ville " << n;
        cerr << " doit etre positive ou nulle..." << endl;
        exit(1);
      } else if (tabVille[n-1]->demande() > -0.0001) {
        cerr << "Erreur de lecture : la demande de la ville " << n;
        cerr << " est definie 2 fois..." << endl;
        exit(1);
      } else {
        tabVille[n-1]->demande(d);  //INITIALISE la demande de la ville
        i++;
      }
  }
  if (i != nbVille) {
    cerr << "Erreur de lecture : " << i << " demandes lues et dimension=";
    cerr << nbVille << endl;
    cerr << "Il manque la definition de la demande des villes ";
    for (int j=0; j<nbVille; j++)
      if (tabVille[j]->demande() < -0.001) cerr << j << " ";
    cerr << endl;
    exit(1);
  }
  fclose(f);  
  delete [] lineBuf;
  delete [] nomFichierComplet;
}
//Pour écrire dans un fichier, la fonction fprintf;

Je souhaite corriger les erreurs et implementer les variables qu'il faut, C'EST CA MON PB

[Gre]

Envoyé par simloun

salut
mon probleme est surtout en implementaion, j'arrive pas à mettre les declarations en place, on m'a passé une indication d'un code mais il est bourré d'erreur et je suis incapable de corriger. Je suis PERDU; [...]

Sais tu programmer ?
Sinon c'est peine perdu. TU devrais commencer par un cours.

Dans le cas où tu sais programmer en C
En as tu parlé avec celui qui ta donné ce code ? Ou bien lui non plus ne sait-il pas quoi en faire ?

En général quand un code est mal documenté (document d'analyse, document de conception et commentaires) il finit à la poubelle et on recode tout.

D'où l'importance de faire des efforts quand on code.

Si tu n'as pas le concepteur du code sous la main, peut être devrais-tu tout recommencer. C'est pas bien long ce qu'il y a là, et au moins tu partirais avec tes idées à toi et pas celle d'un autre (ce qui est toujours difficile à interpréter).

Finalement, il doit bien y avoir un informaticien près de chez toi. Ça serait plus pertinent qu'ici où nous allons aligner de longues lignes sans être très clair.

Ton code manque cruellement de beaucoup de chose à vue de nez.

d_ij n'est pas défini... est-ce d[i][j] ? et manque-t-il une boucle ? est-ce bien d_ij ? mais alors qu'est ce que ça représente ?

Pareil pour le i et le j !! Visiblement c'est des objets (ou des enregistrements, ce qui est kiff-kiff-pareil en C++pour ce qui nous concerne) qui ont des méthodes x() et y()... mais qu'est ce que c'est censé faire ?

Difficile de débugger qqchose quand tu ne sais pas ce que tu dois lui faire faire (pour ne pas dire impossible).

[simloun]

C'est vrai, t'as raison, je vais mette tout ça en place et au cas j'y arrive pas à un truc précis, je poserai une question bien précise.
Merci

[argusazure]

Je pense que d_ij est la distance euclidienne entre i et j qui sont des villes. La méthode x() de la classe ville correspond à l'abscisse de la ville.
C'est vrai que c'est un peu top mélangé comme code. C'est pas très agréable de programmer dans "ça". Je te conseille de faire un parser à part pour lire les différent schamps de ton fichier. Le xml est pas mal si tu veux faire quelque chose d'un peu plus propre encore.

Mais pour débugger, c'est avec ton compilateur qu'il faut voir...

[simloun]

dans la classe ville quelle est la différence entre déclarer la classe avec

double x,y;

et

double x();
double y():

[Gre]

Envoyé par argusazure

Je pense que d_ij est la distance euclidienne entre i et j qui sont des villes. La méthode x() de la classe ville correspond à l'abscisse de la ville.
C'est vrai que c'est un peu top mélangé comme code. C'est pas très agréable de programmer dans "ça". Je te conseille de faire un parser à part pour lire les différent schamps de ton fichier. Le xml est pas mal si tu veux faire quelque chose d'un peu plus propre encore.

Mais pour débugger, c'est avec ton compilateur qu'il faut voir...

XML ??
Faut arrêter avec le XML, c'est souvent moche et lourd.
Dans le cas présent il faut préciser le problème, pas rajouter des lourdeurs.

[Gre]

Envoyé par simloun

dans la classe ville quelle est la différence entre déclarer la classe avec

double x,y;

Ce sont deux attributs (ou champs)

double x();
double y():

Ce sont deux méthodes.

Conceptuellement, on préfère passer par des méthodes permettant de modifier et lire les données. Ceci à de nombreux avantages au niveau de la maintenance et de la cohérence interne.
On trouve souvent du code qui accède directement aux données. Très souvent c'est par fainéantise, mais c'est une erreur alors. Très rarement c'est pour un très léger gain dans le programme, qui généralisé peut devenir important. Mais on brise l'encapsulation.

Tu ne sais pas bien programmer en fait n'est-ce pas ?
Comme je t'ai dis, c'est une perte de temps de repartir de ce qui a été fait. Tu ferais mieux de tout refaire et de le documenter pour la prochaine fois.

[simloun]

Merci à tous pour vos conseils; je vais vous dire ce que j'ai fais petit à petit; au fait il s'agit d'écrire une fonction qui lit les renseignement dans un fichier(par exemple le fichier joint), donc il y a le nombre de ville (n), les coordonnées de chaque ville (x,y) et les demande de chaque ville (di) ; j'ai écrit la classe suivante, qu'en pensez vous :

class ville {
int nbVille,i;
double x();
double y();
double d[i];
double CAPACITE:
}

Bien sûr ce n'est QUE le début, on verra pour le reste
ceci paraît-il juste ? si non quelle modification me proposeriez vous ? JE SUIS NUL en programmation et après pas mal d'effort je me suis retourné vers vous. C'est mon dernier joker (avis du public) !!

[Gre]

Envoyé par simloun

[...]qu'en pensez vous :

class ville {
int nbVille,i;
double x();
double y();
double d[i];
double CAPACITE:
}

Des indentations... le peuple veut une bonne présentation !
C'est-à-dire ça

class ville {
    int nbVille,i;
    double x();
    double y();
    double d[i];
    double CAPACITE:
}

Selon l'IDE (environnement de développement intégré) que tu utilises tu as certainement une fonction dans un menu qui permet de remettre tout en forme pour que ce soit joli

Bon sinon ta classe est problématique, tu n'as que des membres privés. Il faut déclarer ce qui est publique (donc accessible à tous le monde même ceux qui ne sont pas une ville).

Je supposes aussi que tu as mis trop de chose dans ta classe. Et que tu as oublié quelques const.

Finalement il serait cool de donner des noms significatifs à tes variables pour qu'on sâche ce quelle représente. Le temps perdu à écrire un nom plus long est très largement récompensé par moins de problème lorsqu'il convient de retrouver ses bugs. Et en même temps, mais là c'est plus discutable, je te conseillerais de mettre des majuscules aux noms de tes classes pour les distinguer des autres types.

Donc

class Ville {
        static int nbVille; // le nombre de villes totales ?
        int numero; // le numero de la ville ?
        double distance_vers[NB_MAX_VILLE]; // distance vers la ville i
        const double CAPACITE: // je ne sais pas à quoi ça sert
    public
        double x(); // position en abscisse
        double y(); // position en ordonnee
}

La on voit que j'ai rajouté static devant int nbVille car c'est une variable qui sera partagé par tous les objets de classe Ville.

Il faut maintenant ajouter une constante NB_MAX_VILLE qui elle aussi sera static car partagée par toutes les villes. Tant qu'à faire CAPACITE devrait aussi être static. Je suppose que tu as oublié les deux champs (attributs) correspondant à l'abscisse et à l'ordonnée de ta ville.

class Ville {
        static const int NB_MAX_VILLE = 100 // nombre maximum de ville
        static const double CAPACITE = 100 // je ne sais pas à quoi ça sert
        static int nbVille; // le nombre de villes totales ?
        int numero; // le numero de la ville ?
        double abscisse, ordonnee ; // les coordonnees de la ville
        double distance_vers[NB_MAX_VILLE]; // distance vers la ville i
    public
        double x(); // recuperation de la position en abscisse
        double y(); // recuperation de la position en ordonnee
}

Finalement pour en faire un fichier « .h » il faudrait que tu rajoutes cela qqs instructions au préprocesseur.

Fichier Ville.h

#ifndef _VILLE_H_
#define _VILLE_H_

class Ville {
        static const int NB_MAX_VILLE = 100 // nombre maximum de ville
        static const double CAPACITE = 100 // je ne sais pas à quoi ça sert
        static int nbVille; // le nombre de villes totales ?
        int numero; // le numero de la ville ?
        double abscisse, ordonnee ; // les coordonnees de la ville
        double distance_vers[NB_MAX_VILLE]; // distance vers la ville i
    public
        double x(); // recuperation de la position en abscisse
        double y(); // recuperation de la position en ordonnee
}
#endif // _VILLE_H_

Maintenant il va falloir coder les fonctions..
Je te fais x() et y() et je te rajoute un constructeur où tu devras chercher un peu

Fichier Ville.cpp

Ville::Ville(double x, double y)
{
    /* Beaucoup de choses à faire ici.
        Dans un premier temps il faut mettre les
        coordonnees dans les bonnes variables (facile)
        puis assigner un numero à la ville (sans
        dépasser le nombre maximum de ville)
        puis calculer sa distance avec les autres villes 
        créée... et là tu vas voir que tu auras un
        problème.
        Il ne faudrait pas oublier de mettre à jour la
        variable contenant le nombre de villes créées.
        on s'en reparle :D
     */
}
double Ville::x() 
{
    // on retourne simplement l'abscisse de la ville
    return abscisse; 
}

double Ville::y()
{
    // on retourne simplement l'ordonnee de la ville
    return ordonnee ;
}

[Coincoin]

Salut,
Il ne faut pas un point-virgule après la classe ? J'ai des mauvais souvenirs d'un compilateur pas clair...

[Gre]

Envoyé par Coincoin

Salut,
Il ne faut pas un point-virgule après la classe ? J'ai des mauvais souvenirs d'un compilateur pas clair...

Oui effectivement. Comme pour un struct. C'est une erreur de ma part.

[simloun]

Merci bp Gre, je vais essayer de comprendre tout ce que tu m'as écris. Il me semble que j'aurais pas mal de boulot je pense rédiger ce que tu m'as écris, ej te tiendrai au courant.

[simloun]

à l'aide de quelques recherches, j'ai remarqué que des documents de ce genre peuvent etre trouvé sur le site de l'ieee xplore; mais je ne connais personne abonné dans le site. et ça sert à rien de s'y abonner pour un seul document. quelqu'un connait il un abonné à l'ieee xplore ?

[argusazure]

Quelque petites habitudes d'écriture qui ne font pas de mal :
Classe ville -> CVille
double x() -> double GetX(void)
double abscisse -> double dX;
static int nbVille -> static int nNbVille

[Gre]

Envoyé par argusazure

Quelque petites habitudes d'écriture qui ne font pas de mal :
Classe ville -> CVille
double x() -> double GetX(void)
double abscisse -> double dX;
static int nbVille -> static int nNbVille

Pas d'accord... d'abord mettre des majuscules à des fonctions n'est pas une très bonne norme.

La notation qui préfixe par le type est loin d'être un plaisir à lire. Elle a d'ailleurs tendance à être mise de côté de plus en plus.
Je suppose qu'on te l'a apprise en classe et que tu l'utilises où tu es maintenant. Mais tu ferais mieux de l'abandonner si tu peux. Un nom précis et clair est 100 fois plus efficace.

Finalement, un nom explicite est mieux qu'un petit nom (x dans dX vs. abscisse)... sans compter que dX c'est pour beaucoup de scientifique un écart sur les abscisses et que donc tu mêles potentiellement le future lecteur.

Par contre mettre get devant l'accesseur est effectivement une bonne idée. De même mettre une majuscule à la classe si tu veux une notation à-la Java. Cependant j'en connais qui n'aime pas ça disant qu'une classe devrait être considéré comme un type normal et donc ne devrait pas avoir de notation distinct (comprendre: pas de majuscule).

C'est l'autodocumentation qui prime.