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.