Plus court chemin (optimisation combinatoire)

Question

Bonjour, J'ai un tp dont le problème est de trouver le chemin le plus court dans un graphe orienté. La résolution de ce problème ne se fait pas à l'aide des algorithmes classiques (comme Dijkstra ou Ford-Bellman), c'est plutôt en utilisant le principe de l'optimisation combinatoire : l'idée est d'explorer tous le chemins possibles entre deux sommets quelconques et ensuite en choisir le meilleur. J'ai déjà défini les données nécessaires. Maintenant, il me reste l'exploration des chemin. Je n'ai pas trouvé un idée comment faire. Je vous présente le code que j'ai écrit: struct Arc{ int pd; //point de départ int pf; // point d'arrivée double poid; //Définir le poid de l'arc void setPoid(double pp) { poid = pp; } //Définir les 2 sommets void setSommets(int a, int b) { pd = a; pf = b; }}; struct Chemin{ int sommet; double distance; Chemin*arcSuivant; //Définir la distance void setDistance(double x) { distance += x; }}; int main(){ cout << "Combien de sommet? "; int n; cin >> n; int i = 0, j = 0, k = 0; double poidtemp; vector arc; arc.resize(n*n); while (i

cptpingu · Answer

Bonjour.

Utiliser une optimisation combinatoire va être bien plus lente qu'un Dijkstra ou un Bellman ! Mais bon si c'est un tp...

L'idée est la suivante:
- Tu généres toutes les possibilités (tous les chemins possibles) du point d'origine au point de destination, en faisant du backtracking.
- Tu représentes cela dans un string, dont tous les numéros de noeuds sont sur deux chiffres, séparés par un espace.
- Une fois que tu as générés l'ensemble de tous les chemins possibles, tu auras un std::string par chemin.
- Ces chemins, tu les mets dans un std::vector (via du .push_back).
Au choix:
-  Tu les tries par ordre croissant (c'est pour le tri que je te disais de forcer tous tes nombres sur deux chiffres).
- Le premier élément de ton tableau trié est ton meilleur chemin.
Ou:
- Tu recherches le std::string le plus court de ton tableau.

Autre solution moins coûteuse en terme de calcul (mais je ne sais pas si ton énoncé te l'autorise):
- Au lieu de mettre chacun des chemins dans un vecteur, tu conserves uniquement le "meilleur" std::string. C'est à dire que tu ne gardes que le std::string le plus court dans ton backtracking. Le std::string résultant est alors le meilleur chemin.

__________________________________________________________________________________________________

Améliorez votre expérience CodeS-SourceS avec ce plugin:
http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

Mus · Answer

Merci beaucoup
Je vais essayer ça et revenir

Mus · Answer

Bonjour, 
cptpingu
Pouvez-vous, si c'est possible, m'expliquer encore à travers une exemple c++? Sur mon code qu'est ce que je doit ajouter ou suuprimer?

cptpingu · Answer

Voici une méthode simple, en C++ (on va utiliser les outils C++ pour se simplifier la vie): - Tout d'abord, on met dans un std::vector, l'ensemble des noeuds. On va supposer que tu identifies chaque noeud par un charactère ('a', 'b', etc...). Donc un std::vector. - Ensuite, tu vas mettre dans un tableau à double dimension, l'ensemble des arcs (il y aura des "trous" mais ce n'est pas grave). C'est en fait une matrice d'ajacence, qui va nous servir plus tard. Tu peux aussi représenter cela via un std::map, mais c'est peut être un peu plus compliqué si tu ne maîtrises pas la STL. - Tu tries ton tableau de noeuds en utilisant la méthode std::sort qui est dans le header . On a besoin de trier le tableau pour générer correctement les permutations. - On génère ensuite toutes les permutations de noeuds possibles, grâce à la fonction std::next_permutation (qui fait vraiment tout le travail). Je te laisse regarder la doc et des exemples de cette fonction sur internet (il faut un std::sort + une boucle do...while pour que ça fonctionne). - Maintenant, à chaque tour de boucle, tu auras une liste de noeuds ordonnée différemment. Si ton premier élément n'est pas ton noeud de départ, tu ne fais rien. - Si le premier noeud est ton noeud de départ, alors tu regardes s'il existe un arc (un lien) entre le premier et le deuxième noeud, puis entre le deuxième et le troisième, etc... jusqu'à atteindre ton noeud d'arrivé. Si tu as réussi à trouver des liens entre tous les noeuds entre ton départ et ton arrivé, alors regarde si la distance entre ton point de départ et d'arrivé (en utilisant le poids de chacun des arcs) est inférieur à la meilleure distance connue (la distance minimale connue est initialisée à +infini, que l'on représente en C++ via: int min = std::numeric_limit::max(), le header est ). Si c'est le cas, la distance minimale devient cette distance, et tu sauvegardes le chemin de "départ-arrivé" dans un tableau temporaire (tableau que tu vides et écrases à chaque fois que tu trouves un meilleur résultat). - Une fois sortie de la boucle des permutations, tu auras normalement le meilleur chemin dans ton tableau temporaire, ainsi que la plus petite distance possible dans ta variable "min". Ps: Tu sembles utiliser des "using namespaces" dans ton code, c'est à proscrire ! Plus d'info ici: http://0217021.free.fr/portfolio/axel.berardino/articles/bon-usage-using-namespace Ps2: Optimisation possible pour plus tard: Ne pas mettre ton noeud de départ dans la liste des noeuds afin de ne pas générer de permutations inutiles. __________________________________________________________________________________________________ Améliorez votre expérience CodeS-SourceS avec ce plugin: http://codes-sources.commentcamarche.net/forum/affich-10000111-plugin-better-cs-2#cptpingu-signature

Plus court chemin (optimisation combinatoire)

4 réponses

Votre réponse

Discussions similaires