1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    septembre 2010
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2010
    Messages : 7
    Points : 6
    Points
    6

    Par défaut Quel type d'algorithme pour couvrir un maximum de nœuds dans un graphe sans dépasser un budget donné ?

    Bonjour à tous,

    Je viens vers vous pour poser une question pour m'aider à orienter mes recherches.

    Je voudrais savoir s'il existe des algorithmes pour trouver dans un graphe de noeuds priorisés un chemin permettant de couvrir le plus de noeuds prioritaires sans dépaser un "coût" et cela à partir d'un point de départ. Attention à la différence des algorithmes que je "connais" déjà comme dijkstra, Voyageur de Commerce..." j'ai quelques différences/contraintes:
    • Pas de point de fin spécifique. Je n'ai qu'un point de départ, peut importe ou le chemin se fini? Je dois juste m'arrêter quand le "coût" est atteint.
    • Je ne cherche pas à passer par tous les noeuds


    Pour donner du contexte, mes noeuds sont des coordonnées géographiques correspondant à des "actions" à faire avec un "poids" correspondant à l'urgence de traitement. Entre chaque nœud, j'ai un "coût" pour m'y rendre (en KM ou en temps) et j'ai besoin de construire un chemin qui me dit : en Xminutes ou Xkm à partir du point Z je peux faire ce chemin qui passe par les points les plus prioritaires et donc traiter ces X actions.
    Pour information il n'est pas question de trouver la meilleure solution mais seulement une "optimale".

    Merci bcp pour vos retours.
    Julien

  2. #2
    Membre émérite
    Homme Profil pro
    Inscrit en
    mai 2008
    Messages
    1 723
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : mai 2008
    Messages : 1 723
    Points : 2 322
    Points
    2 322

    Par défaut

    Bonjour,

    Je prendrais Monte Carlo :
    http://www.developpez.net/forums/d15...s-d-ouverture/

  3. #3
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Quel type d'algorithme

    Bonjour,

    La comparaison des chemins exige la définition de leur efficacité:
    Citation Envoyé par juju0169 Voir le message
    ... mes noeuds sont des coordonnées géographiques correspondant à des "actions" à faire avec un "poids" correspondant à l'urgence de traitement. Entre chaque nœud, j'ai un "coût" pour m'y rendre (en KM ou en temps) et j'ai besoin de construire un chemin qui me dit : en Xminutes ou Xkm à partir du point Z je peux faire ce chemin qui passe par les points les plus prioritaires et donc traiter ces X actions ...
    Quelle fonction mesurera le gain obtenu ? On peut envisager, dans le cas le plus simple, une expression linéaire comme la différence entre le poids des actions accomplies et le coût de la distance parcourue: G = Somme(Pk) - K*Somme(dij) .
    Il faut alors déterminer la constante (K), en évaluant le poids (Pm) d'un nouveau site visité qui, compte tenu de la distance supplémentaire parcourue (DeltaD), conduirait à un gain nul, soit: Pm - K*DeltaD = 0 (1).

    Si l'on accorde un rôle déterminant aux temps d'accès aux sites les plus importants, on peut ne pas compter la longueur du trajet retour, ou d'une manière plus systématique évaluer le coût de chaque étape proportionnellement au poids des sites non encore visités, par une expression du type:
    Cij = dij*Somme(Pk') .

    L'itinéraire peut se construire progressivement, à partir de la position initiale, en ajoutant successivement les divers sites selon l'ordre décroissant de leur poids, et en recherchant à chaque étape la position correspondant au meilleur gain (ou au moindre coût); il aurait pour configuration triangulaire initiale: P0(départ) --- P1 --- P2 .

    (1) Autre amorce possible de l'évaluation, par:
    - le calcul du poids total de l'ensemble P = Sk=1N(Pk) , et
    - l'évaluation du périmètre de la boucle fermée L = 2 * Dmax (double de la distance maximale entre deux points) ou L = (PiPjPk)max (périmètre maximal d'un triangle, si les points ne sont pas trop nombreux).
    L'ordre de grandeur du facteur (K) est donné par le quotient (P/L).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  4. #4
    Membre éprouvé
    Profil pro
    Inscrit en
    avril 2004
    Messages
    653
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations forums :
    Inscription : avril 2004
    Messages : 653
    Points : 938
    Points
    938

    Par défaut Combien de sites ?

    Le choix d'une méthode dépend de façon essentielle de la taille du graphe. Si tu as un petit nombre de sites urgents, une méthode bête peut te donner une bonne solution. Combien en as-tu, en ordre de grandeur ?
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  5. #5
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 488
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 488
    Points : 3 944
    Points
    3 944

    Par défaut

    salut

    cela me fait penser a la recherche de solution pour une partie d'echec ou de dame dans se cas là on utilise
    un algo de type alpha-beta
    cela permet d'explorer toutes les solution possible en faisant l'impasse selon certaine condition
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  6. #6
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Quel type d'algorithme

    Avoir à explorer toutes les solutions possibles n'est peut-être pas souhaitable compte tenu de leur grand nombre (~(N-1)!), d'autant que l'auteur du sujet déclare se satisfaire d'une solution raisonnablement performante:
    ... il n'est pas question de trouver la meilleure solution mais seulement une "optimale" ...
    Un trajet intéressant apparaît rapidement par allongement progressif de la boucle, si l'on donne la priorité aux sites les plus urgents, de poids maximal. L'algorithme s'apparente dans son principe à celui du voyageur de commerce; il n'en diffère que par la comparaison des boucles construites sur un ensemble donné de sommets, dans laquelle interviennent les poids des sites visités, en plus des distances parcourues.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Futur Membre du Club
    Profil pro
    Inscrit en
    septembre 2010
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2010
    Messages : 7
    Points : 6
    Points
    6

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    Avoir à explorer toutes les solutions possibles n'est peut-être souhaitable compte tenu de leur grand nombre (~(N-1)!), d'autant que l'auteur du sujet déclare se satisfaire d'une solution raisonnablement performante:

    Un trajet intéressant apparaît rapidement par allongement progressif de la boucle, si l'on donne la priorité aux sites les plus urgents, de poids maximal. L'algorithme s'apparente dans son principe à celui du voyageur de commerce; il n'en diffère que par la comparaison des boucles construites sur un ensemble donné de sommets, dans laquelle interviennent les poids des sites visités, en plus des distances parcourues.
    Alors dans l'ordre, merci à toutes les réponses et désolé pour le délai (je viens de me rendre compte que l'email associé à mon compte n'est plus le bon, ... bref).
    Alors effectivement, je n'ai pas du tout besoin de la solution optimale (sachant, que je n'avais pour voulu vous noyer de détail, mais de toute façon les "priorités" sont basées sur des éléments incertains/hypothèses, donc cela n'aurait aucun "sens" je pense de choisir l'optimal).

    Pour le reste des réponses, ce qui me pose problème c'est comment appliquer les algos type voyageur sachant que je ne veux (ou plutôt ne peux pas) pas définir un point de fin. C'est une "tournée" et si je choisi un point de fin, j'ai peur de fausser les résultats. Ais-je raison ?

    Du coup, je suis en train de regarder les autres algorithmes que je ne connaissais pas. L'idée de définir la formule de coût me semble être une bonne piste avec peut être juste derrière un algo de proche en proche. Est-ce que l'on peut espérer (si on suppose que les priorités sont bonnes que le chemin "naturellement" tende vers un chemin maximisant les gains ?

    Encore merci pour votre temps.

  8. #8
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 488
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 488
    Points : 3 944
    Points
    3 944

    Par défaut

    salut

    l'apha-beta est une variante de algorithme minmax qui sert justement a explorer toutes les possibilité et à ne garder que la valeur maximal afin de jouer le meilleur coup dans ton cas se n'est pas la somme des valeur de pion mais la somme des coûts
    il te faudra apporter une condition supplémentaire de type si la somme des coût dépasse mon seuil alors je met la somme à une valeur négative et je sort de la boucle.
    de cette manière celui-ci ne seras jamais pris en compte .
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  9. #9
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Quel type d'algorithme

    Je n'ai pas bien compris la précision concernant l'absence de position finale:
    Citation Envoyé par juju0169 Voir le message
    ... je ne veux (ou plutôt ne peux pas) pas définir un point de fin. C'est une "tournée" et si je choisis un point de fin, j'ai peur de fausser les résultats. Ais-je raison ? ...
    mais sans doute s'agit-il d'un faux problème; il y a des sites à visiter selon un ordre d'urgence préétabli, à priori distincts de la position initiale, selon un trajet optimal (on y reviendra) et sans se soucier de l'éloignement de la position ultime, ce qui revient à négliger la longueur du dernier trajet - un retour au point de départ s'impose cependant à tout livreur, quel qu'il soit, et le terme de "tournée" suggère un parcours cyclique.

    1°) Soit par conséquent un nuage de points, constitué de la position initiale (O) et de l'ensemble des sites à visiter, affectés d'un poids non-nul au moins égal à l'unité, et classés par ordre de préséance décroissante.
    On pourra partir d'une boucle triangulaire (OAX) construite sur le site de poids maximal (A) et le site le plus éloigné (X); des variantes excluant l'une des deux positions précédentes (OMX, OAM) conduiront éventuellement, selon le même algorithme, à des solutions différentes qui seront comparées.

    2°) L'accroissement de la boucle se fera par insertion d'un nouveau sommet entre deux autres, déjà reliés par une arête, en envisageant la combinaison de tous les points disponibles avec toutes les arêtes existantes; on retiendra celle correspondant au gain maximal
    G = Somme(Pvisités) - K*Somme(Larêtes), ou plus simplement la plus grande variation
    DeltaG = Pk - K*(dik + djk - dij) .
    C'est à ce niveau qu'intervient, d'une manière spécifique, l'importance relative des divers sites.

    Point délicat: quelle valeur attribuer à la constante (K) ? En effet celle-ci ne doit être ni trop faible, ni trop élevée (ce qui conduirait soit à négliger les distances, soit à leur donner une influence exclusive).
    La définir comme le quotient de valeurs moyennes apparaît comme le meilleur choix: K = Pm / Dm ,
    avec pour le poids moyen: Pm = (1/N)*Sommek=1NPk ;
    la notion de distance moyenne est par contre beaucoup plus malaisée à définir; si l'on peut évaluer l'aire (S) de la région occupée par le nuage de points, il sera possible d'en déduire la distance cherchée par l'expression: Dm = (S/N)1/2 . On aura ainsi pour un nuage pas trop allongé: S ~(Xmax - Xmin)*(Ymax - Ymin) .

    3°) Il faut songer à modifier le trajet obtenu (qu'il s'agisse du résultat final, comme de toute boucle intermédiaire) afin d'en éliminer les défauts, et de le raccourcir; à ce stade, seules les distances interviennent puisque l'on opère sur un ensemble donné de sommets.
    Interviennent deux opérations élémentaires, le décroisement des arêtes (1), et le transfert de sommet (2):

    Nom : 2 Figures ABCD-EFGH.png
Affichages : 127
Taille : 12,7 Ko

    Des variantes sont encore envisageables, dans la mesure où le trajet final dépend du nombre et de la réitération des opérations précitées. Il est d'autant plus court que ces opérations ont été plus nombreuses.

    4°) Les critères de choix appliqués jusque là sont symétriques, donc indifférents au sens de parcours de la boucle. Il existe cependant un moyen de départager tous les résultats obtenus: le second critère proposé dans l'un des messages précédents (#3), fort indigeste (je le reconnais ) et encore inemployé (et pour cause !).
    Voici par exemple quel serait le coût (selon la définition donnée) d'un trajet comportant une étape de longueur variable:

    Nom : Boucle OABCD.png
Affichages : 129
Taille : 5,8 Ko

    # parcours (OABCD): C1 = x*10 + 10*6 + 10*3 + 10*1 + 10*0 = 100 + 10*x ;
    # parcours (ODCBA): C2 = 10*10 + 10*9 + 10*7 + 10*4 + x*0 = 300 .
    Le premier parcours présente le moindre coût lorsque 100 + 10*x < 300 , soit x < 20 : on retrouve ici l'idée conforme à l'intuition, qui consiste à donner la priorité au site le plus urgent, sous réserve qu'il ne soit pas trop éloigné.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Quel type d'algorithme ... ?

    L'intitulé du sujet vient d'être notablement allongé
    Quel type d'algorithme pour couvrir un maximum de nœuds dans un graphe sans dépasser un budget donné
    et cela modifie sensiblement la nature de la recherche.

    Pour s'y adapter, on peut envisager les variantes suivantes:
    a) Exclure la dernière étape (le retour à la position initiale) de toutes les modifications envisagées en (2) et (3).
    b) Partir d'une configuration triangulaire (OAX) dans laquelle (X) représente:
    # soit le point le plus éloigné de (O), mais dont la distance reste en-deçà de la limite imposée par le "budget";
    # soit le point le plus proche de (O), et dont la distance dépasse la limite précédente - il sera éventuellement supprimé, par la suite;
    c) Modifier le trajet selon les procédés décrits en (2) et (3), jusqu'à ce que la longueur totale dépasse la limite permise.
    d) Retrancher l'une des étapes du trajet, et voir quelle est la plus grande distance parcourue compatible avec la condition imposée.
    La solution retenue en dernier lieu parmi toutes celles vérifiant (Dtotale < Limite) pourra aussi correspondre au gain maximal (G) - autre choix envisageable.

    En l'absence de boucle, le critère décrit en (4) n'a plus lieu d'être.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Quel type d'algorithme pour couvrir un maximum de nœuds dans un graphe sans dépasser un budget donné ?

    Le recours à une méthode de Monte Carlo, suggéré par phryte (#2), peut se révéler intéressant au prix de quelques instructions complémentaires, afin de favoriser l'accès aux sites les plus importants, et de raccourcir autant que possible le nouveau trajet obtenu.
    Ces corrections deviennent indispensables lorsque les points deviennent suffisamment nombreux: et tu n'a donné sur ce point aucune indication, malgré la demande de Nebulix (#4).

    Les (N) sites à parcourir étant affectés d'un poids entier non-nul mesurant leur importance,
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    TYPE LstNW = ARRAY[1..N] OF Word;
    CONST ListeP: LstNW = (9, 7, 5, 5, 5, ... 1, 1);
    VAR ListeS: LstNW; 
    
    ListeS:= ListeP;
    on constitue une liste de tirage de longueur égale au poids total de l'ensemble Ptot = Sommek=1N(Pk) , et initialisée comme suit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    VAR ListeT: ARRAY[1..Nmax] OF Word;          // Nmax > Ptotal
    i:= 0;
    FOR k:= 1 TO N DO 
      IF ListeS[k]>0 THEN
        FOR m:= 1 TO ListeS[k] DO BEGIN
                                    Inc(i); ListeT[i]:= k
                                  END;  
    Ptot:= i;
    FOR i:= Ptot+1 to Nmax DO ListeT[i]:= 0;
    Un tirage aléatoire permet de sortir au hasard l'un des sites, avec une probabilité proportionnelle à son poids; ce coefficient est immédiatement annulé dans la liste des poids, en vue des tirages ultérieurs.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    j:= Random(Ptot); // valeur aléatoire in [0..Ptot - 1]
    Inc(j); m:= ListeT[j]; ListeS[m]:= 0;
    Les deux premiers tirages vont donner une boucle triangulaire, incluant la position initiale.
    À partir du 3me, il faudra procéder à chaque étape à une correction éventuelle de trajectoire, selon ce qui a déjà été indiqué (#9, 3°), et recommencer ainsi jusqu'à ce que la longueur maximale soit atteinte.

    Le procédé devrait conduire à une séquence de solutions relativement bonnes, qu'il suffirait par la suite de départager.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  12. #12
    Futur Membre du Club
    Profil pro
    Inscrit en
    septembre 2010
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2010
    Messages : 7
    Points : 6
    Points
    6

    Par défaut

    Bonjour à tous,

    Alors en vrac, concernant la quantité de points je suis dans l'ordre d’environ 250 points. Plus globalement, je me rends compte que la problématique est au final plus complexe que identifié au début et il va surtout falloir quelques jour le temps que j'analyse plus en détail toutes vos réponses.

    Du coup, ne doutant pas que j'ai assez d'info pour avancern je note le poste en "Résolu" et je reposerais une question au besoin.

    Encore merci pour votre temps.
    Julien

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Quel type de referencement pour mon site ?
    Par jiojioforever dans le forum Référencement
    Réponses: 4
    Dernier message: 28/11/2006, 13h24
  2. quel type de conception pour un serveur?
    Par hisoka dans le forum Développement
    Réponses: 2
    Dernier message: 17/11/2006, 20h47
  3. quel type de champ pour un tableau serializé
    Par lodan dans le forum PHP & MySQL
    Réponses: 2
    Dernier message: 17/11/2006, 15h37
  4. quel type de serveur pour mon site marchand
    Par yoyoviper dans le forum Dépannage et Assistance
    Réponses: 4
    Dernier message: 09/11/2006, 09h07
  5. [SQL Server] Quel type de champ pour du commentaire
    Par brmartin dans le forum Langage SQL
    Réponses: 6
    Dernier message: 24/07/2006, 13h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo