Discussion :

[toubiba]

Bonjour

je travail sur un tp sur le problème du voyageur du commerce
le Calcul d’un circuit hamiltonien optimal ou approché dans un
graphe complet pondéré.

je suis bloqué sur cette question je sais pas comment la faire.
si quelqu'un peut m'aider en me donnant des indices ou des exemples pour la résoudre

1) Mise des sommets dans une file de priorité (implantée par un tas) pour un accès rapide au
meilleur sommet à ajouter au parcours, selon les algorithmes.

merci

[ternel]

Ceci est un énoncé.
C'est bien.
Qu'en comprends-tu?
Que signifie chaque terme de l'énoncé: sommet, file de priorité (priority queue en anglais), tas, meilleur sommet?

[toubiba]

je ne sais pas comment faire pour par exemple la mise des sommets dans une file de priorité
implanter la file de priorité par un tas
je suis encore débutant en graphe je ne sais pas comment faire pour résoudre ça.

[ternel]

Qu'est-ce qu'une file?
Qu'est une file de priorité?
Et un tas?

Spoiler: réponse (ou presque) !

Ce sont trois structures de données permettant de manipuler une collection de choses.
La partie intéressante, ce sont les propriétés de chacune.
La partie problématique, c'est la manière de les réaliser.

Une collection de choses est un Bidule© contenant des choses.
Une file est une collection, donc, avec une entrée, par laquelle on ajoute un élément au contenu, et une sortie d'où on peut retirer un élément du contenu.
La propriété notable c'est qu'on fait sortir les éléments un par un, dans l'ordre d'ajout.

Une file de priorité (ou à priorité) est une collection dont les éléments sortent par ordre de priorité.
Si la priorité d'une telle file, c'est "le plus petit en premier", alors si j'ajoute successivement 7, 3, 4 et 1, les éléments qui sortiront sont 1, 3, 4 et 7.

Un tas est une manière de ranger des éléments, dont le nombre n'est pas connu à l'avance, de façon "relativement" triée, ce qui permer de les utiliser dans l'ordre.
Par cette notion d'ordre, c'est une structure qui permet de coder une file de priorité.

Comment les coder?

[toubiba]

Qu'est-ce qu'une file?
Qu'est une file de priorité?
Et un tas?

Spoiler: réponse (ou presque) !

Ce sont trois structures de données permettant de manipuler une collection de choses.
La partie intéressante, ce sont les propriétés de chacune.
La partie problématique, c'est la manière de les réaliser.

Une collection de choses est un Bidule© contenant des choses.
Une file est une collection, donc, avec une entrée, par laquelle on ajoute un élément au contenu, et une sortie d'où on peut retirer un élément du contenu.
La propriété notable c'est qu'on fait sortir les éléments un par un, dans l'ordre d'ajout.

Une file de priorité (ou à priorité) est une collection dont les éléments sortent par ordre de priorité.
Si la priorité d'une telle file, c'est "le plus petit en premier", alors si j'ajoute successivement 7, 3, 4 et 1, les éléments qui sortiront sont 1, 3, 4 et 7.

Un tas est une manière de ranger des éléments, dont le nombre n'est pas connu à l'avance, de façon "relativement" triée, ce qui permer de les utiliser dans l'ordre.
Par cette notion d'ordre, c'est une structure qui permet de coder une file de priorité.

Comment les coder?

oui je veux savoir comment les coder

[ternel]

Et bien, ce sont des structures classiques, il te suffit de relire ton cours / chercher sur les sites classiques.

En vertu de l'article IV-N de notre charte, que tu as acceptée, toi aussi, nous ne pouvons pas résoudre les exercices.
En prime, je ne sais pas coder de tête un tas, donc, j'irai chercher sur internet.
Du coup, autant te laisser chercher toi même.

Si tu as un peu de code à nous montrer, nous pourrons t'aider à l'améliorer, à le corriger. Mais certainement pas à l'écrire à ta place.