Discussion :

[juju0169]

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

[phryte]

Bonjour,

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

[wiwaxia]

Bonjour,

La comparaison des chemins exige la définition de leur efficacité:

... 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(P_k) - K*Somme(d_ij) .
Il faut alors déterminer la constante (K), en évaluant le poids (P_m) d'un nouveau site visité qui, compte tenu de la distance supplémentaire parcourue (DeltaD), conduirait à un gain nul, soit: P_m - K*DeltaD = 0 ⁽¹⁾.

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:
C_ij = d_ij*Somme(P_k') .

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: P₀(départ) --- P₁ --- P₂ .

(1) Autre amorce possible de l'évaluation, par:
- le calcul du poids total de l'ensemble P = S_k=1^N(P_k) , et
- l'évaluation du périmètre de la boucle fermée L = 2 * D_max (double de la distance maximale entre deux points) ou L = (P_iP_jP_k)_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).

[Nebulix]

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 ?

[anapurna]

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

[wiwaxia]

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.

[juju0169]

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.

[anapurna]

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 .

[wiwaxia]

Je n'ai pas bien compris la précision concernant l'absence de position finale:

... 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(P_visités) - K*Somme(L_arêtes), ou plus simplement la plus grande variation
DeltaG = P_k - K*(d_ik + d_jk - d_ij) .
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 = P_m / D_m ,
avec pour le poids moyen: P_m = (1/N)*Somme_k=1^NP_k ;
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: D_m = (S/N)^1/2 . On aura ainsi pour un nuage pas trop allongé: S ~(X_max - X_min)*(Y_max - Y_min) .

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):



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:



# parcours (OABCD): C₁ = x*10 + 10*6 + 10*3 + 10*1 + 10*0 = 100 + 10*x ;
# parcours (ODCBA): C₂ = 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é.

[wiwaxia]

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 (D_totale < 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.

[wiwaxia]

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 P_tot = Somme_k=1^N(P_k) , 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.

[juju0169]

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