Discussion :

[yannou63360]

Bonjour à tous,

Je poste ici car je développe en c++, mais mon problème est plutot lié à de la logique.

Je suis en train d'implémenter l'algorithme 2opt pour le problème du TSP.

Avant de rentrer dans le vif du sujet je vais vous expliquer ce qu'est 2opt et le TSP afin que tout le monde puisse voir de quoi je parle.

TSP :

C'est le problème plus connu en france comme étant le problème du voyageur de commerce.

L'énoncé est simple : étant donné un ensemble de n villes nous devons trouvé la tournée de moindre coût permettant de passer par l'ensemble des villes une et une seulle fois tout en revenant à la ville de départ.

D'un point de vue théorie des graphes nous pourrions dire que nous souhaitons trouver le cycle de moindre coût.

2opt :

Le principe de cet algorithme est simple.

Nous devons tout d'abord trouvée une solution initiale, Sinit, calculée aléatoirement ou par un quelconque autre moyen.

Pour ma part j'ai initialisé Sinit de façon aléatoire.

Puis Tant que le nombre d'itération maximal n'est pas atteind :

-nous cassons 2 arrétes aléatoirement de notre cycle initial et nous reconstruisons un nouveau cycle différent du précédent.

En modifiant si possible le sens de certaines arrétes c'est a dire si nous avons 0 1 2 3 4 et que nous supprimons 01 et 34 nous obtenons alors 0 3 2 1 4.

-si le nouveau cycle a un cout inférieur au précédent alors nous le concervons

-sinon nous concervons le cycle avant transformation.

Cela permet donc d'optenir un cycle de coût minimal.

Plusieurs méthodes d'implémentation existent :

La méthode naïve :

Elle consiste à créer un cycle, c, et sa copie, cp, avec leurs coûts associé cout, et coutc.

De cette façon les modifications ne sont apportées qu’à la copie.

Si le cout de la copie coutp est inférieur à cout alors c est modifié sinon on réinitialise cp à c et nous réitérons.

Cette méthode à pour principal défaut d'être très gourmande en ressource à cause de la réinitialisation de cp.

Pour parer cela une autre méthode à été trouvée :

Elle consiste à ne pas faire de copie nous effectuons la modification directement sur notre cycle de base.

Et si les modifications engendrent un meilleur cycle alors nous le conservons, sinon nous refaisons un 2 opt pour revenir à l'état initial.

Mon problème arrive a ce moment la. Mais pour être plus clair je vais vous parler de mes structures de données.

Mon cycle est enregistré dans un tableau de taille n (n=nombre de villes).

Par exemple après initialisation mon cycle est : 0 1 2 3 4, pour n=5.

Ce qui veut dire que les arrêtes 01 ; 12 ; 23 ; 34 et 40 composent mon cycle.

Les coûts de ces arrêtes sont dans un matrice de taille n*n dont la diagonale est de valeur "infinie" (pour éviter les boucles).

Et donc pour calculer le coût de ma solution initiale je fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for(int i=0; i<nb_ville; i++)
    cbest+=cost[cyclebest[i]][cyclebest[(i+1)%nb_ville]];

Après quoi je commence les modifications sur mon cycle et je calcule le cout des arrête enlevées est supérieur au coût des arrêtes ajoutées.

Et le problème est bien la je n'arrive pas à calculer ses coûts.

Après plusieurs essais je me suis arrêté à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
if(max==nb_ville-1&&min==0)
        {
            for(int i=min; i<max; i++)
            csuppr+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
        else
        {
 
                for(int i=min; i<max; i++)
            csuppr+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
if(cmax==nb_ville-1&&cmin==0)
        {
            for(int i=cmin; i<cmax; i++)
            cnv+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
        else
        {
 
        for(int i=cmin; i<cmax+1; i++)
            cnv+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }

Je me doute bien que le problème vient de mes indices de tableau mais je ne vois pas ce qui ne va pas.

La mise à jour de cbest ce fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
if(cnv<csuppr)
  cbest-=(csuppr-cnv);

Je vous mets bien sur mon code source :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
using namespace std;
 
int main()
{
    cout<<"\n    /*********************************************************************/"<<endl;
    cout<<"    /*                                                                   */"<<endl;
    cout<<"    /*                         2opt pour le TSP                          */"<<endl;
    cout<<"    /*                                                                   */"<<endl;
    cout<<"    /*********************************************************************/\n"<<endl;
 
 
    //Création et initialisation des variables :
    int nb_ville=0;
    cout<<"Nombre de villes a parcourir : ";
    do
    {
        cin>>nb_ville;
    }
    while(nb_ville<1);
 
 
    int cptite=0, min=0, cmin=0, max=0, cmax=0, temp=0, itecur=0, cbest=0, csuppr=0, cnv=0;
    int cost[nb_ville][nb_ville], cyclebest[nb_ville];
 
    //Le palier est le nombre maximal d'itération que fait notre algorithme aprés chaque amélioration de notre cycle :
    float palier=log(2)*(nb_ville*(nb_ville-3)/2);
 
    srand(time(NULL));
 
    //Création d'un graphe complet sans boucle
    for(int i=0; i<nb_ville; i++)
        for(int j=i; j<nb_ville; j++)
            if(i!=j)
                cost[i][j]=cost[j][i]=rand()%(2*nb_ville)+1;
            else //Les sommets qui ne sont pas joignables sont à une distance infinie des autres.
                cost[i][j]=(signed)INFINITY;
 
    //Affichage de la matrice des coûts :
    cout<<"\nCOUTS :"<<endl;
    for(int i=0; i<nb_ville; i++)
    {
        for(int j=0; j<nb_ville; j++)
            cout<<cost[i][j]<<"\t\t";
 
        cout<<endl;
    }
 
    //Création et affichage du cycle initial :
    for(int i=0; i<nb_ville; i++)
        cyclebest[i]=i;
 
    cout<<"Cycle inital : "<<endl;
    for(int i=0; i<nb_ville; i++)
        cout<<cyclebest[i]<<"\t";
 
    //Calcul et affichage du coût initial :
    for(int i=0; i<nb_ville; i++)
        cbest+=cost[cyclebest[i]][cyclebest[(i+1)%nb_ville]];
 
    cout<<"\n\nCout du cycle initial : "<<cbest<<"."<<endl;
 
    int cbest2=0; //Cette variable permet de voire la véritable valeur que devrait avoir cbest aprés chaque amélioration du cycle.
 
    //Recherche d'une solution de meilleur qualité en utilisant 2-opt :
    while(itecur<palier)
    {
        //Réinitialisation des variables :
        temp=rand()%nb_ville;
        csuppr=cnv=0;
 
        //Pour éviter les itérations sans modification de notre cycle nous tirons 2 nombres aléatoires différents :
        do
        {
            max=rand()%nb_ville;
        }
        while(temp==max);
 
        //Organisation du nouveau cycle créé et calcul de Delta :
        min=cmin=(temp<max)?temp:max;
        max=cmax=(temp>max)?temp:max;
 
        if(max==nb_ville-1&&min==0)
        {
            for(int i=min; i<max; i++)
                csuppr+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
        else
        {
 
            for(int i=min; i<max; i++)
                csuppr+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
 
 
        while(min<max)
        {
            temp=cyclebest[min];
            cyclebest[min]=cyclebest[max];
            cyclebest[max]=temp;
 
            min++;
            max--;
        }
 
        if(cmax==nb_ville-1&&cmin==0)
        {
            for(int i=cmin; i<cmax; i++)
                cnv+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
        else
        {
 
            for(int i=cmin; i<cmax+1; i++)
                cnv+=cost[cyclebest[(i-1+nb_ville)%nb_ville]][cyclebest[i%nb_ville]];
        }
 
        //Si le nouveau cycle est de meilleur qualité nous le sauvegardons :
        if(cnv<csuppr)
        {
            cbest-=(csuppr-cnv);
            itecur=0;
            cbest2=0;
 
            for(int i=0; i<nb_ville; i++)
                cbest2+=cost[cyclebest[i]][cyclebest[(i+1)%nb_ville]];
 
            cout<<"\nCycle courant : "<<endl;
            for(int i=0; i<nb_ville; i++)
                cout<<cyclebest[i]<<"\t";
 
            cout<<"\ncnv :"<<cnv<<"\tcsuppr :"<<csuppr<<"\tcbest :"<<cbest<<"\tcbest2 :"<<cbest2<<endl;
        }
        else
        {
            while(cmin<cmax)
            {
                temp=cyclebest[cmin];
                cyclebest[cmin]=cyclebest[cmax];
                cyclebest[cmax]=temp;
 
                cmin++;
                cmax--;
            }
            itecur++;
        }
        cptite++;
    }
 
    //Affichage de meilleur cycle trouvé, ainsi que de son coût et du nombre d'itérations nécessaires à sa découverte :
    cout<<"\nCYCLE_BEST :"<<endl;
    for(int i=0; i<nb_ville; i++)
        cout<<cyclebest[i]<<"\t";
 
    cout<<"\n\nCyclebest a pour valeur : "<<cbest<<"."<<endl;
    cout<<"\nPalier : "<<palier<<"."<<endl;
    cout<<"\nNombre total d'iteration : "<<cptite<<"."<<endl;
 
    return 0;
}

Je code avec Code::Blocks 10.05 sous windows 7.

En vous remerciant d'avance pour vos réponses.

[therwald]

"je n'arrive pas à calculer ces coûts" est un tantinet imprécis... quel est le symptôme exact?

• plantage (message d'erreur please)?
• valeur aberrante (en quoi, merci de préciser)?
• ...

[yannou63360]

Pour te répondre j'obtiens des valeurs aberrantes.
Je m'en suis rendu compte grâce à mon affichage de cbest et de cbest2 ces deux variables sont différentes alors qu'elles ne devraient pas vu que ce sont la même donné calculée différemment.

[Bousk]

Bonjour,

certaines bases sont à revoir.

Les déclarations de cost (et tous les tableaux qui suivent) sont interdites (et devrait au moins générer un warning). Ce n'est pas de cette façon que l'on déclare un tableau. Sa dimension doit être connue à la compilation. Cette écriture serait des VLA (variable-length-array), authorisée par une certaine norme C, retirée depuis il me semble, mais dans tous les cas : une mauvaise pratique.


Partant de là, rien ne me surprend, puisque l'accès aux cases de ces tableaux est synonyme de comportement indéfini.

[yannou63360]

bizarrement je n'ai aucun warning ...
et je devrais faire quoi pour parer ce qui est selon toi un problème?

[Iradrille]

bizarrement je n'ai aucun warning ...
et je devrais faire quoi pour parer ce qui est selon toi un problème?

Hello,

utiliser un vector par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
inline size_t xyToInd(size_t x, size_t y, size_t size) { return y*size+x; }
 
//...
 
std::vector<int> cost(nb_ville*nb_ville), cyclebest(nb_ville);
// utilisation identique, sauf tableau à 1 dimension au lieu de 2 pour cost
cost[xyToInd(x, y, nb_ville)] = ...;
// au lieu de
cost[x][y] = ...;

[yannou63360]

Merci pour vos réponses qui ne correspondaient pas à ma question ...
Grâce à cela j'ai pu résoudre mon problème.

Cordialement