Discussion :

[hyuga33]

Bonjour,
je cherche à coder un branch and bound en C++.
En fait ça fais une semaine que j'ai découvert le C++ et j'ai du coder une heuristique. J'ai réussi mais ça été difficile!!!
Maintenant j'aimerais coder le branch and bound sauf que il me reste que jusqu'à vendredi pour rendre mon projet de recherche. Si j'ai ce code je pense que j'aurais fais le tour du problème.
J'ai essayer de le faire mais je n'y arrive pas... donc à l'aide!!!!!
Je cherche un code si possible.
Merci d'avance pour vos réponses!

[3DArchi]

En fait ça fais une semaine que j'ai découvert le C++ et j'ai du coder une heuristique. J'ai réussi mais ça été difficile!!!

Et bien maintenant, tu dois être expert pour coder ton algo
Sérieusement, quel est ton problème ? Où bloques-tu ? Qu'as-tu déjà codé ?

[hyuga33]

Hé!hé! j'aurais bien aimé être un expert!
Je dois coder l'algorithme du branch and bound pour mon problème.
J'ai coder une manière d'avoir une borne supérieure correcte.
Ensuite il faut que je code le reste.
J'ai une matrice 33x33, un sommet de départ(ici 0). Mon problème est un problème de voyageur de commerce et les arcs (i,j) de la matrice représente la distance entre les villes i et j. Il faut que je retourne le chemin optimal en ayant parcourue 10 arcs.
C'est là que le branch and bound intervient.
Je suis partis sur:
-partir d'un vecteur V ayant 0 comme premier élément
-prendre la borne supérieure calculer plus haut
-a l'étape suivante: ajouter un noeud i au vecteur V puis calculer le cout de déplacement entre les noeuds présents dans V
-Si le cout est inférieure à la borne sup, alors on continue jusqu'à avoir onze éléments dans le vecteur sinon on essaye les autres solutions
-Si à cette étape le cout total de déplacement est inférieure à la borne sup alors ce cout devient la borne sup et le vecteur V devient le vecteur solution
-Ensuite, on regarde pour toutes les combinaisons possibles.
Donc je vois pas trop comment coder et encore moins comment gérer les combinaisons déja vues ou pas.
J'espére avoir été assez clair. N'hésite pas à demander d'avantages d'explication.
Merci.

[Sylvain Togni]

Le problème que tu a à résoudre est de trouver le plus court chemin composé de 10 arcs et partant de la ville 0, c'est bien ça ?

Pour l'implémentation en C++ je te conseil d'utiliser une std::priority_queue pour gérer la liste des chemins en cours, un std::list<int> pour stoker un chemin et un std::vector<bool> pour marquer les villes déjà visitées (cela suffit pour gérer les combinaisons déjà vues il me semble).

N'hésite pas à nous montrer ton code pour qu'on puise t'aider d'avantage !

[hyuga33]

Oui, je dois bien trouver le chemin le plus court partant de 0 en 10 arcs.
Je commencerai à coder ce soir, pas le temps aujourd'hui, donc je vous tiendrais au courant de mon avancée. Je vais essayer avec les aides que tu m'as apportées.
Merci.

[jblecanard]

Salut

C'est un peu bourrin de faire de la théorie des graphes en C++ après une semaine de pratique !

Bon en tout cas, si tu veux des structures de données, il y a tout ce qu'il faut dans la BGL. L'algo Branch And Bound n'est pas implémenté dans la BGL, mais j'imagine que tu seras noté sur son implémentation justement...