TSP : Tavelling Salesman Problem

Version imprimable

15/12/2016, 15h46
toubiba

TSP : Tavelling Salesman Problem

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
15/12/2016, 16h02
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?
15/12/2016, 16h31
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.
16/12/2016, 13h39
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?
16/12/2016, 15h21
toubiba

Citation:

Envoyé par 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?

oui je veux savoir comment les coder
16/12/2016, 15h39
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.
16/12/2016, 16h09
toubiba

Citation:

Envoyé par 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.

moi je n'ai pas demandé d’écrire le code a ma place.
j'ai demandé comment les coder c'est a dire par quoi je commence il faut créer quoi au début.
en tout cas merci pour votre aide.
16/12/2016, 16h46
ternel
Il faut commencer par poser ton vocabulaire de travail.

Tu veux une file de priorité des noeuds du graphe.
Bien, ca veut dire qu'il y aura au moins:
- un typedef ... graph.
- un typedef ... graph_node
- un typedef ... graph_node_priority_queue
- une fonction qui dit de deux noeuds lequel est prioritaire. Je plagie la signature de la comparaison de chaines: int graph_node_priority_compare(graph_node const*, graph_node const*)
Je ne sais pas encore ce qu'il y aura dedans. Par contre, partant de là, j'imagine que je vais devoir manipuler cette file.
Il faut donc aussi créer:
- une fonction qui me dit si la file est vide. bool graph_node_priority_queue_empty(graph_node_priority_queue const *);
- une fonction qui récupère le noeud le plus important de la file de priorité: graph_node* graph_node_priority_queue_pop(graph_node_priority_queue *);
- une fonction qui ajoute un noeud dans la file: void graph_node_priority_queue_pop(graph_node_priority_queue *, graph_node*);
A présent, je commence à cerner un peu mieux ma question.
Et que mettre dans chaque typedef? et bien, des structures qui contiendront ce qu'il faut pour pouvoir coder les fonctions dont j'ai besoin.

Viens alors une autre chose importante. Qui fait le tri: l'ajout dans la file ou la récupération?
La réponse est dans l'énoncé de ton exercice. Un tas est une structure triée, donc il faut qu'à la fin de l'ajout, et de la récupération, elle soit toujours triée.
En conséquence, les deux fonctions doivent s'en occuper.

On arrive au point suivant: comment faire un tas.
réponse: je ne sais toujours pas, va chercher cette information dans ton cours, auprès de ton professeur (qui sera heureux de répondre à une question prouvant que tu réfléchis au problème), ou sur un site d'algorithme ou de conception. (voire, sur wikipedia, pour une première idée).
30/12/2016, 21h43
piponux

Bonjour, modestement, je réponds, n'étant ni informaticien, ni étudiant en informatique, à la phrase suivante :

Citation:

On arrive au point suivant: comment faire un tas.

cette vidéo m'a fait comprendre le principe et l'implémentation d'un tri par tas.

https://www.youtube.com/watch?v=7AwB...?v=7AwBHw6Z6SU