Discussion :

[LeProgInvétéré]

Bonsoir,
je sais que c'est peut-être tard pour demander de l'aide sur ce genre de problème, mais étant donné le caractère urgent de la chose et mon manque de solution, je décide de me tourner vers la communauté, une fois n'est pas coutume.

Je dois pour demain soir terminer une résolution du problème du voyageur du commerce, qui n'est plus à présenter. J'ai fais des recherches sur des algorithmes et des bouts de code existant, et je n'arrive pas à les adapter à ce qu'il me faut.

Voici ce que j'ai, de manière très grossière : une classe représentant un point, dont la base est la suivante (et incomplète mais, je pense, suffisamment compréhensible) :

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
typedef long double ldouble;
 
class Point
{
	public:
		Point();
		Point(ldouble x, ldouble y);
		~Point();
 
		inline ldouble getX() const { return m_x; }
		inline ldouble getY() const { return m_y; }
		inline bool getParcours() const { return m_parcours; }
 
		inline void setX(ldouble x) { m_x = x; }
		inline void setY(ldouble y) { m_y = y; }
		inline void setParcours(bool parcours) { m_parcours = parcours; }
 
		inline ldouble distance(ldouble x, ldouble y) const { return (sqrt((pow((x - m_x), 2) + pow((y - m_y), 2)))); }
 
		friend std::ostream& operator<<(std::ostream& os, Point const& src);
		friend std::istream& operator>>(std::istream& is, Point& src);
 
	private:
		ldouble m_x;
		ldouble m_y;
		bool m_parcours;
};

Ainsi que deux fonctions que voici :

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
bool parcoursComplet(std::vector<Point> tab)
{
	bool estParcouru = true;
 
	for(std::vector<Point>::iterator it=tab.begin();it!=tab.end();++it)
		estParcouru = ((estParcouru) && (it->getParcours()));
 
	return estParcouru;
}
 
 
std::vector<Point> voyageurCommerce(char const* nomFichier)
{
	InfosPoint iPt1;
	InfosPoint iPt2;
	std::vector<Point> tabLu = lireFichier(nomFichier);
	std::vector<Point> tabRes;
 
	iPt1.position = 0;
	iPt2.position = 0;
	iPt1.distanceMin = 5000000000000000000000000000.0;
	iPt2.distanceMin = 5000000000000000000000000000.0;
 
	while((!parcoursComplet(tabLu)))
	{
		for(size_t i=0;i<tabLu.size();++i)
		{
			if((i != iPt1.position) && (!tabLu[i].getParcours()))
			{
				if(tabLu[iPt1.position].distance(tabLu[i]) < iPt2.distanceMin)
				{
					iPt2.position = i;
					iPt2.distanceMin = tabLu[iPt1.position].distance(tabLu[i]);
				}
			}
		}
 
		tabLu[iPt2.position].setParcours(true);
		tabRes.push_back(tabLu[iPt2.position]);
		iPt1.position = iPt2.position;
		iPt2.distanceMin = 5000000000000000000000000000.0;
	}
 
	return tabRes;
}

Et une structure dont voilà la définition :

Code :

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

1
2
3
4
5
struct InfosPoint
{
	size_t position;
	ldouble distanceMin;
};

En plus d'autres menues fonctions pour la lecture et l'écriture dans des fichiers.
J'ai, en entrée, la chose suivante : un fichier (au format .in3) qui contient, dans sa première ligne, le nombres de points qu'il contient dans les lignes suivantes. Les lignes suivantes contiennent chacune les coordonnées en X et en Y d'un point, des nombres réels (donc à stocker dans des doubles).

En sortie, je dois avoir un fichier avec, en première ligne, le même nombre de points que pour le fichier d'entrée, en deuxième ligne, la distance de parcours totale et, sur les autres lignes, les points triés dans l'ordre de parcours.

J'ai un programme donné par mon prof pour vérifier la validité des fichiers de sortie, et ce dernier me donne une moyenne de 0/20 (super note, n'est-il pas ?), ainsi que pour le premier fichier d'entrée, contenant 20 points, un parcours trop long, et pour les autres fichiers d'entrée, contenant respectivement 100, 1000 et 10000 points, des points manquants.

Pourriez-vous apporter une correction à mon code, s'il vous plaît ?
Même des conseils pour me mettre sur la voie me seraient grandement utiles.

Merci d'avoir pris le temps de lire ce pavé, j'espère pouvoir compter sur vos retours !

[Andéol]

Bonjour,

Mon conseil, pour le moment, est d'établir l'algorithme que vous souhaitez utiliser en pseudo-code. Ne vous posez pas la question de l'implémentation et des structures requises pour le moment. Quelle est la méthode de parcours ? Vérifiez à la main que votre méthode marche, sur un exemple avec 1 unique point, puis 2, puis 3.
L'implémentation ne vient qu'après.

Un second conseil, et c'est lié, et de commenter votre propre code. On pense souvent au commentaires comme à quelque chose qui ne sert que pour que les autres puissent lire le code, mais c'est plus que ça. Quand vous déclarez une variable, adjoignez-lui un commentaire qui décrit précisément (mathématiquement) ce que cette variable représente. Cela vous force à clarifier les idées et permet de réaliser quand deux variables sont nécessaires au lieu d'une.
Par exemple, dans votre code, que représente m_parcours très exactement ? Le nom même de la variable me fait pensez que son rôle a certainement changé en cours d'implémentation. Sinon, elle se serait appelé m_parcouru.
Même chose pour les méthodes. On a là une méthode parcoursComplet, je conseille d'écrire la documentation d'une telle méthode avant même de l'implémenter.

Détail : Cette fonction pourrait prendre un argument en référence constante std::vector<Point> const & tab
Ca ne change pas grand chose, en-dehors des perfs, mais ça aide aussi à débuguer, puisque le compilateur se plaindra si la méthode modifie le contenu de tab par accident (qui n'a jamais utilisé un signe "=" au lieu de "==" ?)