Calcul de chemins dans un graphe

Fermé

Programath Messages postés 5 Date d'inscription jeudi 9 décembre 2021 Statut Membre Dernière intervention 17 décembre 2021 - Modifié le 26 août 2022 à 15:18
mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 - 26 août 2022 à 15:07

Bonjour a tous,

J'ai un travail sur lequel nous réfléchissons depuis deux semaines avec mon groupe et sur lequel nous bloquons en permanence quelques soient les manières de l'aborder.

il se présente comme cela:

Le programme doit contenir la carte des villes et des routes suivant le plan donné. Il demandera à un voyageur sa ville de départ et son budget et évaluera tous les chemins possibles utilisant le réseau routier pour aller à Rome.

La traversée de certaines villes permet au voyageur de gagner de l’argent tandis que d’autres vont lui infliger une taxe de séjour. Tout voyageur part avec une somme initiale fixée (son budget) mais le voyage s’arrête quand il ne peut plus
payer la taxe de séjour.

Attention : il est interdit lors d’un même voyage de passer 2 fois dans la même ville.

Résultat attendu :

Partie 1 : Le programme devra être capable d’interroger l’utilisateur pour
simuler les différentes étapes d’un chemin possible pour aller de la ville de
départ (de son choix) jusqu’à Rome. Il calculera alors la distance parcourue, les
villes traversées et le prix du voyage. Si un chemin ne permet pas d’aller jusqu’à
Rome, le programme s’arrête.

Voici notre main et le cpp que nous avons "réussi" à faire. Si quelqu'un y arrive même un peu j'avoue que cela nous aiderait beaucoup.

Merci d'avance si c'est possible.

#include <iostream>
#include <vector>
#include "Voyage.h"

using namespace std;

struct ville
{
    string nom;
    double tax;
    double position[2];

};
/*void tab_ville() //Pour le tableau de ville, il faut qu'on fasse comme pour le td5
{
    vector<string> villes(10);//mon 1er test (une sorte de tableau de vecteur pour enregistrer le nom des villes)
    villes[0]={"A"};
    villes[1]={"B"};
    villes[2]={"C"};
    villes[3]="D";
    villes[4]="E";
    villes[5]="F";
    villes[6]="G";
    villes[7]="H";
    villes[8]="Rome";

    //for (int i=0; i<10; i++)
     //cout<<villes[i]<<endl;
}*/
int saisie_ville()
{
    int choix;

    cout<<"Choisissez une ville: "<<endl;
    cout<<"Choix 1: Ville A"<<endl;
    cout<<"Choix 2: Ville B"<<endl;
    cout<<"Choix 3: Ville C"<<endl;
    cout<<"Choix 4: Ville D"<<endl;
    cout<<"Choix 5: Ville E"<<endl;
    cout<<endl;
    do
    {
        cout<<"Saisissez votre choix: ";
        cin>>choix;
    }while (choix<1 || choix>5);
    return choix;
}


int taxe()
{
    int tab[]={10,-50,-50,20};
    int nb=tab[2];
    return nb;
}

#include <iostream>
#include <vector>
#include <cstring>
#include "Voyage.h"

using namespace std;

int main()
{
    vector<string> Nom_villes={"A","B","C","D"};
    int choix, idx;
    string p;
    do
    {
        choix=saisie_ville();
        switch (choix)
        {
            case 1:
                cout<<"Ville de depart: ";
                cin>>p;
                idx=-1;
                for (int i=0; i<Nom_villes.size();i++)
                {
                    if (Nom_villes[i]==p)
                    {
                        idx=i;
                        cout<<"Ville trouve en position "<<idx<<endl;
                        break;
                    }
                }
                if (idx==-1)
                    cout<<"Ville non trouvé..."<<endl;
                break;

            case 2:
                cout<<"Ville de depart: ";
                cin>>p;
                idx=-1;
                for (int i=0; i<Nom_villes.size();i++)
                {
                    if (Nom_villes[i]==p)
                    {
                        idx=i;
                        cout<<"Ville trouve en position "<<idx<<endl;
                        break;
                    }
                }
                if (idx==-1)
                    cout<<"Ville non trouvé..."<<endl;
                break;

                case 3:
                cout<<"Ville de depart: ";
                cin>>p;
                idx=-1;
                for (int i=0; i<Nom_villes.size();i++)
                {
                    if (Nom_villes[i]==p)
                    {
                        idx=i;
                        cout<<"Ville trouve en position "<<idx<<endl;
                        break;
                    }
                }
                if (idx==-1)
                    cout<<"Ville non trouvé..."<<endl;
                break;
        }
        cout<<endl;
    }while(choix!=0);


    //saisie_ville();
    return 0;
}

Configuration: Windows / Chrome 96.0.4664.93

A voir également:

Calcul de chemins dans un graphe
Calcul moyenne excel - Guide
Formule de calcul excel - Guide
Logiciel calcul plancher bois gratuit - Télécharger - Architecture & Déco
Logiciel gratuit calcul surface m2 - Télécharger - Outils professionnels
Logiciel gratuit calcul valeur nutritionnelle - Télécharger - Santé & Bien-être

2 réponses

Réponse 1 / 2

Dalfab Messages postés 706 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 2 novembre 2023 101
9 déc. 2021 à 22:14

Deux semaines à plusieurs pour arriver à ça!

Lisons le début de l'énoncé : "Le programme doit contenir la carte des villes et des routes ..."
Il y a des villes et des routes, donc :
- on essaie de se représenter comment les villes et les routes sont reliées,
- ensuite on se pose sur comment gérer cela
- et ensuite on commence à écrire du code.
Donc vous devriez commencer par les premières étapes.

Réponse 2 / 2

mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 7 752
26 août 2022 à 15:07

Bonjour,

Le sujet est vieux mais il est marrant, alors voici quelques idées pour démarrer.

Avant de démarrer, un peu de terminologie :

Sommet = les villes dans ce problème. L'ensemble des sommets est noté V.
Sommet source = la ville de départ
Sommet cible = la ville de destination (par exemple, Rome)
Arc = les routes connectant deux villes adjacente. L'ensemble des sommets est noté E.
Graphe = ensemble des sommets et des arcs (dans ton cas, la carte routière)
Chemin = une séquence d'arcs consécutifs allant d'un sommet source à un sommet cible
Cycle = un chemin dont le sommet source et le sommet cible sont identique
Boucle = cycle n'impliquant qu'un seul arc
Poids d'un arc = le coût à payer pour traverser un arc. Si les poids sont définis sur les sommets, alors peut se ramener à des poids installés sur des arcs en considérant le coût installé sur le sommet cible de l'arc.
Graphe pondéré = Graphe muni d'une structure de poids (qui donne à chaque arc un poids).

Ensuite, il faut se poser quelques questions sur le problème que l'on veut résoudre. En fonction de celui-ci, des algorithmes sur étagère permettent de répondre immédiatement au problème dans un graphe pondéré.

Que veut-on optimiser ? Cela induit une algèbre de poids.
- La distance ?
- Le coût financier ?
- Les deux, selon un ordre lexicographique (par exemple le prix, puis à prix égal, la distance) ?
- Est-ce que cette algèbre de poids permet la formation de cycle absorbant ?
Que veut-on déterminer ?
- Les plus courts chemin entre une source et tous les autres sommets (atteignables) du graphe ? Ou les plus courts chemins, quelle que soient la source et la destination ?
- Pour chaque couple source destination :
  - Le plus court chemin ?
  - Tous les chemins (sans boucle) ?

Concernant la première question, si le coût est la seule métrique prise en compte, alors un cycle absorbant peut être formé. Si on optimise d'abord le coût puis la distance, des arcs négatifs peuvent apparaître (tous ceux dont le coût financier est négatif). Si on n'optimise que la distance ou que la distance est la première des deux métriques à optimiser, alors "tout va bien" sous réserve qu'il n'y ait pas d'arc dont la distance kilométrique est nulle.

Si le graphe ne comporte pas d'arc de poids négatif (et donc de cycle absorbant), on peut utiliser l'algorithme de Dijkstra. Il se calcule en O(|V|+|E|). En C++, l'algorithme de Dijkstra est implémenté dans la BGL (boost graph library).
Si le graphe ne comporte pas des arcs de poids négatifs mais pas de cycle absorbant, on peut utiliser de Bellman Ford (une source) ou l'algorithme de Floyd Warshall (pour tout sommet source). L'algorithme de Bellman Ford se calcule en O(|V|.|E|). En C++, l'algorithme de Bell Ford est implémenté dans la BGL (boost graph library).
Sinon, il faut énumérer les chemins et rejeter ceux qui engendre un cycle (en particulier de poids négatifs), puisque dans ton problème tu cherches des chemins sans cycle et sans boucle.

Vue la manière dont est formulé le problème, j'ai l'impression que tu es dans le troisième cas.

Algorithme naïf

On énumère tous les chemins possibles et rejeter les chemins mal formés (ceux comportant un cycle et ceux dont le coût est trop élevé étant donné le budget initial) avec un algorithme de branchement.

S = ensemble S de paires (chemin partant de s, budget restant), initialisé à {([s], budget initial)}, où s désigne le sommet de départ.
R = ensemble S de paires (chemin, budget restant) à destination de t = "Rome", initialisé à l'ensemble vide.
Tant que S est non vide
- S' = ensemble vide
- Pour chaque paire (p, b) de S
  - Soit u le dernier sommet de p
  - Pour chaque sommet v voisin de u
    - Si le coût k_uv de (u, v) <= b et si v n'est pas dans déjà dans p (critère de rejet)
      - Ajouter dans S' la paire (p + (u, v), b - k_uv), où p + (u, v) désigne le chemin obtenu en concaténant l'arc (u, v) à la suite du chemin p
      - Si v == t
        
        Ajouter (p + (u, v), b - k_uv) dans R
- S = S'
Retourner R

Terminaison : Le nombre de sommet de G est fini. L'algorithme de considère que des chemins sans boucle et donc de taille au plus |V|. Le nombre de chemins sans boucle est fini. Chaque itération traite un nouveau chemin sans boucle. Il y a donc un nombre fini d'itérations, et donc l'algorithme termine.

Justesse : L'algorithme parcourt tous les chemins bien formés (sans boucle et à budget positif), en particulier ceux à destination de Rome.

Complexité : Si on se restreint au graphe tel qu'il existe au plus un arc entre deux sommets arbitaires, le cas le plus défavorable est quand le graphe forme une clique tel que les contraintes de budget n'écarte aucun chemin (par exemple, pas de taxe de séjour). L'algorithme proposé considère les chemins commençant par s et suivi de n'importe quel arrangement de sommet (autre que s). La somme des arrangements A(n, k) pour k allant de 0 à n est en O(n!), donc l'algorithme est en O((|V|-1)!), autant ça coûte un bras.

Algorithme "malin"

Précision préalable, l'algorithme malin ne répond pas à la question telle que tu l'as formulée, car on se propose ici de ne considérer qu'au plus un chemin de s à t au lieu de tous les chemins (bien formés) de s à t.

Pour cela, on peut simplement adapter l'algorithme de Bellman Ford en ajoutant le critère de rejet vérifiant que le budget reste positif et que le chemin est sans boucle. Comme on rejette les chemins avec des boucles, les cas qui font "planter" l'algorithme de Bellman Ford ne surviennent pas et l'algorithme ainsi modifié calcul un résultat juste.

La complexité devient alors O(|V|.|E|) (soit en O(|V|^2) s'il y a au plus un arc entre chaque paire de sommet), ce qui est clairement bien moins cher que O((|V|-1)!). Mais on aura qu'un seul chemin (un arbitraire chemin arbitraire parmi les chemins optimaux).

Bonne chance

Discussions similaires

Chemin Logo du site de la Cité de l'espace

exo pix

EXCEL - Calcul automatique de Fin de contrat et période d'essai

application pouvant calculer les matériels de plaquiste

un logiciel de calcul pour poutrelles et hourdis avec beaucoup d

Discussions similaires

Newsletters