Problème avec mon programme du plus proche voisin

Version imprimable

bonsoir à tous,

je voudrais implémenter un programme qui permet d'avoir un cycle hamiltonien de poids minimum en se basant sur l'algorithme du plus proche voisin dont voici le code:

Code:

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
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
 
int main(){
#define NBSOMMETS 6
printf("coucou\n");
int f,g;
int T[NBSOMMETS][NBSOMMETS]= {0,5,8,4,3,2,5,0,4,2,1,3,8,4,0,7,5,4,4,2,7,0,9,8,3,1,5,9,0,4,2,3,4,8,4,0};
for (f=0;f<NBSOMMETS;f++){
    for(g=0;g<NBSOMMETS;g++){
 
printf(" %d\t", T[f][g]);
}
printf("\n");
}
int c;
int w,x,y,dist,tmp,z;
int min,i,j,l,m,nb,h,a;
 
#define true 1
#define false 0
typedef int bool;
bool cycle;
int visite[NBSOMMETS];
int parcours[NBSOMMETS];
for(a=0;a<NBSOMMETS;a++){ parcours[a]=999;
                         }
 
for(j=0;j<NBSOMMETS;j++)
{
visite[j]=0;
}
/* Initialisation du generateur aleatoire */
i = rand()%(NBSOMMETS);
visite[i]=1;
parcours[0]=i;
int s,q,max;
max=0;
for(s=0;s<NBSOMMETS;s++){
  for(q=0;q<NBSOMMETS;q++){
  if (T[s][q]>max){
     max=T[s][q];}
     }
     }
 
min=max;
h=0;dist=0;
m=0;
while(!cycle){       
for (l=0;l<NBSOMMETS;l++) { if (T[i][l]!=0){if (T[i][l]<=min) && (visite[l]==0)  {  min = T[i][l];  if (min==T[i][l]){tmp=l;}}}}
 
visite[tmp]=1;
i=tmp;
 
h=h+1;
parcours[h]=i;
 
m=0;
while(m<NBSOMMETS){ if (visite[m]==1){ nb=nb+1;}  m++;}
 
if (nb==NBSOMMETS)
{cycle=1;}
else
{cycle=0;}
}
for(c=0;c<NBSOMMETS;c++){
printf("le sommet %d", parcours[c]);
printf("\n");
}
for(w=0;w<NBSOMMETS-1;w++){
x=parcours[w];
y=parcours[w+1];
dist=dist+T[x][y];
}
printf("la distance %d", dist);
printf("\n");
return 0;
}

la table parcours est censée contenir les sommets par lesquels passe le cycle hors que lors de l'exécution il ne rempli que le premier sommet, je ne sais pas ou est l'erreur.
quelqu'un aurait une solution??
merci.

Met les balises CODE et indente ton programme stp.

Code:

1
2
 
int T[NBSOMMETS][NBSOMMETS]= {0,5,8,4,3,2,5,0,4,2,1,3,8,4,0,7,5,4,4,2,7,0,9,8,3,1,5,9,0,4,2,3,4,8,4,0};

Ne fonctionnera pas.

Code:

1
2
3
 
int T[NBSOMMETS][2]= {{0,5},{8,4},{3,2},{5,0},{4,2},{1,3},{8,4},{0,7},{5,4},{4,2},{7,0},{9,8},{3,1},{5,9},{0,4},{2,3},{4,8},{4,0}};
int T[2][NBSOMMETS]= {{0,5,8,4,3,2,5,0,4,2,1,3,8,4,0,7,5,4,4,2},{7,0,9,8,3,1,5,9,0,4,2,3,4,8,4,0}};

Après, je ne sais pas exactement comment tu veux ranger tes données.
Voici deux exemples après, adaptes-les à ta situation

en fait tu dois considérer cela :

Code:

1
2
3
4
5
 
T[nb_ligne][nb_colonne] = {1er élément, 2ème élément, ..., n ième élément};
T[0][nb_colonne] = {1er élémentA, ...., n ième élémentA};//1er élément de T[[nb_ligne][nb_colonne]]
//donc
T[nb_ligne][nb_colonne] = {{1er élémentA, .... n ième élémentA}, ... n ième élément};

bonjour,
merci neckara pour votre réponse.
j'ai effectivement changé la déclaration de ma matrice comme vous me l'avez demandé mais j'ai toujours le même problème mon programme ne remplit pas la table parcours[NBSOMMETS]!!
je vous repasse le code complet en espérant que quelqu'un trouve ou est le problème.

Code:

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
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
 
int main()
{
#define NBSOMMETS 6
    int f, g;
    int T[NBSOMMETS][NBSOMMETS] = { {0, 5, 8, 4, 3, 2}, {5, 0, 4, 2, 1, 3}, {8, 4, 0, 7, 5, 4}, {4, 2, 7, 0, 9, 8}, {3, 1, 5, 9, 0, 4}, {2, 3, 4, 8, 4, 0} };
    int w, x, y, dist, tmp, z, c, s, q, max;
    int min, i, j, l, m, nb, h, a;
#define true 1
#define false 0
    typedef int bool;
    bool cycle;
    int visite[NBSOMMETS];
    int parcours[NBSOMMETS];
 
    for (a = 0; a < NBSOMMETS; a++) {
	parcours[a] = 999;
    }
    for (j = 0; j < NBSOMMETS; j++) {
	visite[j] = 0;
    }
/* Initialisation du generateur aleatoire */
 
    i = rand() % (NBSOMMETS);
    printf("la valeur aleatoire %dn", i);
    visite[i] = 1;
    parcours[0] = i;
    max = 0;
    for (s = 0; s < NBSOMMETS; s++) {
	for (q = 0; q < NBSOMMETS; q++) {
	    if (T[s][q] > max) {
		max = T[s][q];
	    }
	}
    }
    min = max;
    h = 0;
    dist = 0;
    m = 0;
    while (!cycle) {
	for (l = 0; l < NBSOMMETS; l++) {
	    if (T[i][l] != 0) {
		if (T[i][l] <= min && visite[l] == 0) {
		    min = T[i][l];
		    if (min == T[i][l]) {
			tmp = l;
		    }
		}
	    }
	}
	visite[tmp] = 1;
	i = tmp;
	printf("la nouvelle valeur de i %dn", i);
	printf("n");
	h = h + 1;
	parcours[h] = i;
	m = 0;
	while (m < NBSOMMETS) {
	    if (visite[m] == 1) {
		nb = nb + 1;
	    }
	    m++;
	}
	if (nb == NBSOMMETS) {
	    cycle = 1;
	} else {
	    cycle = 0;
	}
    }
/*afficher le parcours (cycle) ne fait pas un cycle pour l'instant*/
    for (c = 0; c < NBSOMMETS; c++) {
	printf("l %d", parcours[c]);
	printf("n");
    }
    for (w = 0; w < NBSOMMETS - 1; w++) {
	x = parcours[w];
	y = parcours[w + 1];
	dist = dist + T[x][y];
    }
    printf("la distance %d", dist);
    printf("n");
    return 0;
}

merci.

01/03/2012, 10h34
souviron34

première remarque : tes variables ne sont pas initialisées. Or on voit des "while (!cycle)"..

@Neckara

Citation:

Code:

int T[NBSOMMETS][NBSOMMETS]= {0,5,8,4,3,2,5,0,4,2,1,3,8,4,0,7,5,4,4,2,7,0,9,8,3,1,5,9,0,4,2,3,4,8,4,0};

Ne fonctionnera pas.

Si, dans ce cas : NBSOMMETS == 6 et le tableau est alors entièrement initialisé explicitement
C'est une possibilité équivalente à l'expression entièrement encadrée de {} (comme dans les exemples que tu cites ensuite) :

Code:

1
2
3
4
5
6
7
int T[NBSOMMETS][NBSOMMETS]= { {0,5,8,4,3,2},
                               {5,0,4,2,1,3},
                               {8,4,0,7,5,4},
                               {4,2,7,0,9,8},
                               {3,1,5,9,0,4},
                               {2,3,4,8,4,0}
                             };

Par contre, si l'initialisation est partielle, par exemple avec NBSOMMETS ==7, la première forme est équivalente à

Code:

1
2
3
4
5
6
7
8
int T[7][7]= { {0,5,8,4,3,2,5},
               {0,4,2,1,3,8,4},
               {0,7,5,4,4,2,7},
               {0,9,8,3,1,5,9},
               {0,4,2,3,4,8,4},
               {0,4,2,3,4,8,4},
               {0,0,0,0,0,0,0}
             };

et la seconde à

Code:

1
2
3
4
5
6
7
8
int T[7][7]= { {0,5,8,4,3,2,0},
               {5,0,4,2,1,3,0},
               {8,4,0,7,5,4,0},
               {4,2,7,0,9,8,0},
               {3,1,5,9,0,4,0},
               {2,3,4,8,4,0,0},
               {0,0,0,0,0,0,0}
             };

01/03/2012, 12h51
lesnulles

merci pour vos réponses,
@souviron34,
vous voulez dire que je dois initialiser toutes mes variables??? ou bien vous parlez de la variable booléenne "cycle"??

mon problème c'est que quand j'initialise la variable cycle à 0 il me fait une boucle infinie donc il ne rempli pas la table parcours ni la table visite (c'est cette table visite qui permet d’arrêter la boucle, c'est a dire quand touts ses éléments sont à 1, cycle est remise à 1 et la boucle while s’arrête)!!

je ne vois toujours pas où est l'erreur!!!
d'autres propositions??
merci
01/03/2012, 14h33
Bousk

Pourrais-tu indenter le code correctement ?
C'est illisible.

Tu utilises une variable non initialisée pour réaliser une boucle while. Ne vois-tu pas dans cette seule phrase qu'il y a un sérieux souci ?
Avec cette indentation c'est pas facile à se rendre compte, mais j'imagine bien où se situe la boucle et pourquoi. Même si je n'ai pas suivi les accolades.

Initialiser une variable est ~~souvent~~ toujours une bonne idée. Sinon tu l'utilises comment ? tu attends quelle valeur ? indéterminée !
Et travailler avec une valeur indéterminée c'est pas aisé.

Code:

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
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
 
#define NBSOMMETS 6
#define true 1
#define false 0
typedef int bool;
 
int main(){
     printf("coucou\n");
     int f,g;
     int T[NBSOMMETS][NBSOMMETS]={
                 {0,5,8,4,3,2},
                 {5,0,4,2,1,3},
                 {8,4,0,7,5,4},
                 {4,2,7,0,9,8},
                 {3,1,5,9,0,4},
                 {2,3,4,8,4,0}};
     for (f=0;f<NBSOMMETS;f++){
          for(g=0;g<NBSOMMETS;g++)                   
               printf(" %d\t", T[f][g]);
           printf("\n");
      }
      int i;
      int visite[NBSOMMETS];
      int parcours[NBSOMMETS];
      for(i=0;i<NBSOMMETS;i++)
      {
              parcours[i]=999;
              visite[i]=0;
      }
/* Initialisation du generateur aleatoire */
       i = rand()%(NBSOMMETS);
       visite[i]=1;
       parcours[0]=i;
       int s,q,max;
       max=0;
       for(s=0;s<NBSOMMETS;s++)
               for(q=0;q<NBSOMMETS;q++)
                      if (T[s][q]>max)
                              max=T[s][q];
        min=max;
        h=0;dist=0;
        m=0;
        while(!cycle){       
                 for (l=0;l<NBSOMMETS;l++)
                         if (T[i][l]!=0)
                                  if (T[i][l]<=min) && (visite[l]==0)
                                  {
                                            min = T[i][l];
                                            if (min==T[i][l])
                                                        tmp=l;
                                   }
           }
           visite[tmp]=1;
           i=tmp;
           h=h+1;
           parcours[h]=i;
           m=0;
           while(m<NBSOMMETS){
                  if (visite[m]==1)
                           nb=nb+1;
                  m++;
           }
           if (nb==NBSOMMETS)
                  cycle=1;
           else
                  cycle=0;
     }
     for(c=0;c<NBSOMMETS;c++)
           printf("le sommet %d\n", parcours[c]);
     for(w=0;w<NBSOMMETS-1;w++)
     {
           x=parcours[w];
           y=parcours[w+1];
           dist=dist+T[x][y];
     }
     printf("la distance %d\n", dist);
     return 0;
}

J'ai essayé d’endenter mais c'est horrible!
Essaye déjà de diviser tout ceci en plusieurs petites fonctions.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void afficher(int **tab, int ligne, int colonne)
{
            int i =0, j = 0;
            while(i != ligne)
            {
                     while(j != colonne)
                     {
                                  printf("%d\n", *((tab+colonne*i)+j));
                                  j++;
                      }
                     printf("\n");
                     i++;
            }
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
bool isvisite(int *tab, int colonne)
{
       int i = 0;
        while(i != colonne)
        {
                if (visite[m]==0)
                       return false;
               i++;
        }
        return true;
}

Code:

1
2
3
4
5
6
7
8
9
10
 
int maximum(int **tab, int ligne, int colonne)
{
    int i = 0, j = 0, max = 0;
       for(i=0;i<NBSOMMETS;i++)
               for(j=0;j<NBSOMMETS;j++)
                      if (T[i][j]>max)
                              max=T[i][j];
    return max;
}

Code:

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
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
 
#define NBSOMMETS 6
#define true 1
#define false 0
typedef int bool;
 
int main(){
     printf("coucou\n");
     int f,g;
     int T[NBSOMMETS][NBSOMMETS]={
                 {0,5,8,4,3,2},
                 {5,0,4,2,1,3},
                 {8,4,0,7,5,4},
                 {4,2,7,0,9,8},
                 {3,1,5,9,0,4},
                 {2,3,4,8,4,0}};
     afficher(T, NBSOMMETS, NBSOMMETS);
      int i;
      int visite[NBSOMMETS];
      int parcours[NBSOMMETS];
      for(i=0;i<NBSOMMETS;i++)
      {
              parcours[i]=999;
              visite[i]=0;
      }
/* Initialisation du generateur aleatoire */
       i = rand()%(NBSOMMETS);
       visite[i]=1;
       parcours[0]=i;
       int max = maximum(T, NBSOMMETS, NBSOMMETS);
       int min = max;
        int nb = NBSOMMETS;
        int tmp;
        while(isvisite(visite, NBSOMMETS)){
                 for (l=0;l<NBSOMMETS;l++)
                         if (T[i][l]!=0 && T[i][l]<=min && visite[l]==0)
                         {
                                 min = T[i][l];
                                 if (min==T[i][l])//toujours vrai
                                        tmp=l;//tmp toujours égal à 1
                         }
           }
           i = tmp;
           visite[i]=1;
           h++;
           parcours[h]=i;
     }
     for(c=0;c<NBSOMMETS;c++)
           printf("le sommet %d\n", parcours[c]);
     for(w=0;w<NBSOMMETS-1;w++)
     {
           x=parcours[w];
           y=parcours[w+1];
           dist=dist+T[x][y];
     }
     printf("la distance %d\n", dist);
     return 0;
}

01/03/2012, 22h12
anacharsis
salut !

je ne retire rien des critiques précédentes et j'en ajoute une : la prolifération des noms de variables (de boucle) utilisées une seule fois est insuportable !

mais ton programme n'a qu'une paire de grosses fautes (il y en a peut-être d'autres que j'ai corrigé sans m'en rendre compte en refaisant l'indentation) :

cycle doit être initialisé (à false) avant d'entrer dans la boucle
min doit être initialisé (à max) à l'entrée de la boucle
Code:

1 2 3 4 5 m = 0; cycle = false; while (!cycle) { min = max; for (l = 0; l < NBSOMMETS; l++) {
A+

merci à tous pour vos réponse:ccool:,

j'ai modifié le code en tenant compte de certaines de vos remarques, juste une précision pour anarchasis ma variable min doit changer à chaque itération de la boucle while donc l'initialisation doit se faire à l'extérieur de la boucle.
le problème reste le même mon programme boucle indifiniment, il ne remplit pas la table visite ni parcours d'ailleurs et donc la condition d’arrêt n'est jamais atteinte!
je vous repasse le code si vous avez d'autres remarques n'hésitez pas

Code:

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
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
 
 
int main(){
 
#define NBSOMMETS 6
typedef enum {
        true  = (1==1),
        false = (1==0),
} bool;
int T[NBSOMMETS][NBSOMMETS]= {{0,5,8,4,3,2},{5,0,4,2,1,3},{8,4,0,7,5,4},{4,2,7,0,9,8},{3,1,5,9,0,4},{2,3,4,8,4,0}};
int c,w,x,y,dist,tmp,z,f,g,s,q,max,min,i,j,l,m,nb,h,a;
bool cycle;
 
/*initialisation des variables*/
h=0;
dist=0;
m=0;
max=0;
cycle =false;
int visite[NBSOMMETS];
int parcours[NBSOMMETS];
 
/*initialisation de la table parcours*/
for(a=0;a<NBSOMMETS;a++){
                          parcours[a]=999;
                         }
/*initialisation de la table visite*/
for(j=0;j<NBSOMMETS;j++){
                         visite[j]=0;
                         }
 
/* Initialisation du generateur aleatoire */
//srand( (unsigned) time(&t) );
i = rand()%(NBSOMMETS);
 
printf("la valeur aleatoire %d\n",i);
 
visite[i]=1;
parcours[0]=i;
 
/*recherche de la valeur max de la matrice*/
for(s=0;s<NBSOMMETS;s++){
  for(q=0;q<NBSOMMETS;q++){
                           if (T[s][q]>max){
                                             max=T[s][q];
                                             }
                           }
                         }
min=max;
/*boucle while */
while(!cycle){
 
 
for (l=0;l<NBSOMMETS;l++)
 {
  if (T[i][l]!=0)
  {
     if (T[i][l]<=min && visite[l]==0)  
     { 
                       min = T[i][l]; 
                        }}}
                        if (min==T[i][l])
                        {
                                         tmp=l;
                                        }
 
 
visite[tmp]=1;
i=tmp;
h=h+1;
parcours[h]=i;
m=0;
 
/*vérifier si toute la table visite est à 1*/
while(m<NBSOMMETS)
  { 
                  if (visite[m]==1)
                  { 
                    nb=nb+1;
                   } 
      m++;
   }
 
if (nb==NBSOMMETS){
                  cycle=true;
                  }
else{
                  cycle=false;
                  }
 
}
/*fin de la boucle while*/
 
for(w=0;w<NBSOMMETS-1;w++){
                           x=parcours[w];
                           y=parcours[w+1];
                           dist=dist+T[x][y];
                           }
 
printf("la distance %d", dist);
printf("\n");
return 0;
}

Citation:

j'ai modifié le code en tenant compte de certaines de vos remarques, ....

Mais pas de toutes, hélas :
- la présentation du code est toujours épouvantable : indentation et position des délimiteurs de blocs { et } fantaisistes.
- multiplications inutiles de variables dont on ne sait plus à quoi elles servent surtout avec des identificateurs à la gomme :
int c,w,x,y,dist,tmp,z,f,g,s,q,max,min,i,j,l,m,nb,h,a; .

Si tu veux une aide, la première chose à faire est de ne pas décourager les lecteurs en leur facilitant la lecture de ton code par une bonne présentation.

Néammoins, on peut déchiffrer péniblement des anomalies :

-
Code:

1 2 3 4 typedef enum { true = (1==1), false = (1==0), } bool;
Que vient faire la deuxième ','?

-
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 for (l=0;l<NBSOMMETS;l++) { if (T[i][l]!=0) { if (T[i][l]<=min && visite[l]==0) { min = T[i][l]; }}} if (min==T[i][l]) { tmp=l; } visite[tmp]=1;
(Merci pour la présentation :zekill:, mais elle n'est sans doute pas étrangère à l'erreur). A la fin de la boucle for, l vaut NBSOMMETS. Alors le if de la ligne 9 teste un élément hors du tableau :T[i][NBSOMMETS] : plantage possible selon la valeur de i mais code incorrect dans tous les cas et si on ne plante pas, tmp est soit non initialisé, soit égal à NBSOMMETS et plantage à la ligne 15

-
Code:

1 2 3 4 5 6 7 8 while(m<NBSOMMETS) { if (visite[m]==1) { nb=nb+1; } m++; }
Où nb a t-il été initialisé ?

04/03/2012, 19h12
lesnulles

bonsoir à tous,

merci pour votre aide mon code marche enfin:)
vous aviez raison diogene j'avais pas initialisé ma variable nb, et vous aussi anarcharsis il fallait que j'initialise ma variable min=max à l'intérieur de la boucle while, et plus quelque modifications et mon programme marche comme je le voulais :ccool:

encore merci.