Chemins de poids minimal dans un graphe de dépendances

Bonjour à tous,

Je cherche à trouver une solution optimale à un problème de manière polynomiale. Le problème ressemble à une recherche de plus court chemin, mais dans un graphe spécial, que j'aurais envie d'appeler "graphe de dépendances" (si vous avez un terme plus officiel pour ça je suis preneur). Il s'agit d'un graphe pour lequel on peut visiter un nœud si et seulement si un certain ensemble de nœud a déjà été visité.
Par exemple, là ou dans un graphe normal, on peut visiter un nœud N si on a visité "A ou B ou C", dans mon cas, on peut visiter un nœud N si et seulement si on a visité "(A et D) ou (B et E) ou C"
Chaque arête (dépendance) a un certain poids, et je veux calculer l'ensemble des arêtes de poids total minimal nécessaire pour aller d'un certain nœud de départ à un certain nœud d'arrivée.

Voici un exemple de "graphe de dépendances" assez simple. On part de A, et on veut atteindre H avec un coût minimal.
Pièce jointe 661189
Dans cet exemple, on a deux choix de "chemin" (c'est pas vraiment des chemins puisque on passe donc par plusieurs endroits à la fois, mais vous voyez l'idée):
- soit on passe par B, C, D et E. Le coût dans ce cas là est 2 + 7 + 7 + 0 + 3 = 19.
- soit on passe par C, F et G. Le coût dans ce cas là est 7 + 3 + 1 + 9 = 20.
On aimerait donc trouver la 1ère solution.

Voilà, je n'ai pas trouvé d'algorithme sur internet pour ce problème, mais ne connaissant pas quels mots-clés utiliser pour la recherche, je pourrais très bien avoir raté une solution. Quelqu'un connaît un algo ou a des idées pour résoudre ce problème ? Il me faudrait un algo polynomial. Donc en n^3, n^4... ça ne me dérange pas tant que ce n'est pas exponentiel. Au passage, dans mon cas, les poids seraient seulement des 0 ou 1, mais je ne sais pas si ça rend les choses plus facile.

Merci d'avance pour votre expertise !

1) L'aspect polynomial vs exponentiel.
Je pense que ce qui est important, c'est de connaître les conditions d'utilisation qu'on envisage, et le comportement de son algo dans ces conditions.
Un algo polynomial avec t = 200 * n^4 sera plus lent qu'un algo exponentiel de type t = 1.1^n jusqu'à n=300 à peu près.
2) Je pense que la première étape de ton traitement, ça devrait être créer des points 'multiples'.
Par exemple, un point BC ; cout(A,BC)=cout(A,B)+cout(B,C) et cout(BC,D)=cout(B,D)+cout(C,D)

Et en fait, l'autre question qui vient avant cette recherche de coût minimal, c'est : comment sont stockées ces dépendances. A quoi ressemble le modèle de données ?

Merci tbc92 pour votre retour,

J'avoue que dans un 1er temps, je présentais le problème de manière générale, puisque si un algorithme connu existe, ce sera certainement pour ce problème général et pas pour mon cas spécifique. Mais puisque personne n'est intervenu pour le moment pour dire "Ah ben ta problématique, c'est XXX et elle se résout avec l'algorithme de XXX", je vais maintenant rentrer plus dans les détails.

Je dois dans les faits résoudre le problème une seule fois, pour un cas spécique, donc je peux affirmer que je voudrais trouver la solution optimale pour ces valeurs spécifiques:
- soit N = 6 (c'est ce qui m'intéresse, mais je serai curieux d'étudier la question pour d'autres valeurs si possible)
- le graphe a 3^N=729 noeuds
- chaque noeud peut être visité au maximum de 2^N = 64 manières différentes avec un coût de 0, chaque manière nécessitant que 2 autres noeuds donnés soient visité. Autrement dit, un noeud A peut être visité si on a visité un certain nombre de paires (B et C) ou (C et D) ou ... que je suis en mesure de donner
- chaque noeud peut également être visité au maximum de 2^N = 64 autres manières différentes avec un coût de 1, chaque manière nécessitant que 2 autres noeuds donnés soient visité. Idem.
Et parmi tous ces noeuds, à partir d'un noeud de départ, je dois parcourir le moins de "dépendances coûteuses" possible pour atteindre 2^N=64 noeuds donnés. Sachant que si je n'ai pas précisé avoir plusieurs arrivées, c'est parce que ça revient à avoir un unique nouveau noeud d'arrivée qui a pour dépendance l'ensemble de ces 2^N noeuds.
Bref, avec tout ça, on arrive à 730 noeuds et de l'ordre de 50000 dépendances
Donc ce n'est clairement pas envisageable avec de l'exponentiel, même si c'est un "faible" exponentiel. Mais j'ai un peu exagéré en disant que j'acceptais de "gros" polynomial. Si je disais ça, c'est parce que je dois faire le calcul qu'une fois puisque c'est pour résoudre un problème concret. Donc ça ne me dérange pas que ça prenne des heures, mais il faut pas que ça prenne toute ma vie ^^

Concernant votre décomposition avec des points "multiples", je comprends tout à fait qu'on puisse vouloir introduite des noeuds intermédiaires, surtout si ça permet de se ramener à un graphe normal. En revanche, je ne comprends pas votre suggestion. Par exemple, quand votre dites "coût(BC)", votre n'entendez là pas la même chose que "coût(B,C)" ? Ou il s'agit peut-être d'un coût associé au "point multiple BC", dans quel cas qu'est-ce qu'il représente ?

Et concernant le "modèle de données", rien n'est déterminé, je pars de zéro puisqu'il ne s'agit pas de s'intégrer dans autre chose, mais bien d'avoir directement la réponse pour un scénario précis. Je n'ai quasiment rien codé.
En tout cas, je suis en mesure de calculer pour chaque noeud quelles sont leurs dépendances (notamment les fameuses "paires" dont je parlais). Ensuite, je peux stocker le résultat dans des tableaux, des hashmaps, bref, tout ce qui sera nécessaire pour faire tourner l'algo.

1) J'ai corrigé mon message. Cout(BC) n'avait effectivement aucun sens, c'était Cout(B,C)
2) Partage tes données, via un zip...
3) Comment faire en sorte qu'un algorithme 'exponentiel' ait des performances similaires à un algorithme 'polynomial' ? Tu peux faire une recherche aléatoire dans un premier temps, sans viser à être optimum. Tu vas trouver un chemin avec un coût de 150 par exemple.
Tu vas ensuite utiliser un algorithme exponentiel ... mais dès qu'un chemin a un coût de 150, on sait qu'il est voué à l'échec, on l'abandonne.
Et évidemment, il ne faut pas explorer tous les chemins à la même vitesse. Si on explore tous les points qu'on peut atteindre en 1 pas, puis en 2, puis en 3 etc etc... jusqu'à 100 ou 200, on va très vite avoir un nombre de chemins faramineux.

Bonjour tbc92,

[EDIT : les données de ce message sont fausses, cf post #7 pour les bonnes données]

1) Ok, donc l'idée serait de créer un noeud "BC" dont le coût de visite correspondrait au coût qu'il faudrait pour visiter à la fois B et C. Malheureusement, calculer ce "noeud équivalent" n'est pas si simple que cette simple addition dans le cas général, dans la mesure où les noeuds "inputs" ne sont pas forcément reliés.
2) Entendu, si tu es prêt à faire des expérimentations de ton côté. J'ai donc codé aujourd'hui de quoi générer les graphes. Voici donc les graphes pour N=2 à 6 : Pièce jointe 661270. Les fichiers contiennent une dépendance par ligne, avec le coût, les noeuds inputs et le noeud output. Chaque noeud étant indexé de 0 à 3^N-1, auquel se rajoute le fameux noeud final d'index 3^N.
3) D'accord, il y a donc toujours de la réflexion à faire pour imaginer faire fonctionner de l'exponentiel. J'ai d'ailleurs maintenant les dimensions exactes du graphe maintenant que je l'ai généré. Pour N=6, on a donc comme prévu les 729 noeuds + le noeuds final, et 5568 dépendances : 3380 de coût 1 et 2188 de coût 0. En revanche, bonne nouvelle, pas besoin de calculer de solution aléatoire pour trouver un majorant, puisque je suis déjà en mesure d'en fournir un : 57 pour N=6. L'intérêt de cette discussion est justement de voir s'il existe de meilleures solutions que celle là. Maintenant, je ne suis pas pour autant convaincu qu'on peut se permettre d'explorer autant de possibilités, même restreintes avec certaines optimisations. Et c'est d'autant plus frustrant que le problème ne me semble pas être tellement différent d'un problème classique de calcul de chemin minimal qui se résout de manière quasi-linéaire en le nombre d'arêtes :(

Peux tu préciser certaines choses.
Je regarde uniquement le fichier graph6.txt
On a en tout 3 lignes avec Out=32, ce sont :
C=0 IN=30,31 OUT=32
C=1 IN=2,30 OUT=32
C=1 IN=5,27 OUT=32
Donc si on veut aller à 32, soit on est en 31 et on est déjà passé par 30, et le cout est 0, soit on est en 30 et on est déjà passé par 2, et le cout est 1, soit on est en 27 et on est passé par 5, et le cout est 1.
Ca, je pense que c'est bon.
Pour arriver en 729, le cout est 0, mais il faut avoir obligatoirement visité les points 364,365,367, ...

Par contre, problème.
Il y a beaucoup de lignes identiques, par exemple C=0 IN=327,364 OUT=401 ou C=0 IN=1,364 OUT=727
Plus on va vers la fin du fichier, plus on en a.

En fait chaque ligne ne représente pas réellement un chemin.
Notre chemin est imposé, on va de 0 à 729.
Et on s'arrête ou pas à chaque étape, pour prendre le badge correspondant à cet arrêt. S'arrêter à la ville 1 coute 0 point (C=0 IN=0 OUT=1) ; donc on va prendre le badge correspondant, on ne sait pas s'il va servir, mais il ne coute rien.
Pareil, s'arrêter aux villes 2 et 3 ne coute rien, on prend les badges 2 et 3. Plus tard, on prendra les badges 6, 9, 18 ...
On a donc 2 options, prendre le badge de la ville 4 avec un coût 1, ou passer la ville 4 sans s'arrêter.
Arrivé à la ville 5, si on a pris le badge de la ville 4, on a ce badge de la ville 5 gratos (ligne C=0 IN=3,4 OUT=5) , et si on n'a pas le badge de la ville 4, on peut l'acheter (ligne C=1 IN=2,3 OUT=5). Mais ce serait idiot... quitte à dépenser 1 point, on achète le badge de la ville 4, et on a celui de la ville 5 gratos.
Donc arrivé à la ville 5, on a 2 scénarios, soit on a uniquement les badges des villes 0,1,2,3, qui étaient gratuits, sont on a les badges des villes 0,1,2,3,4,5, et on a dépensé 1 point.
Le badge de la ville 6 est gratuit (ligne C=0 IN=0 OUT=6)
Si on a acheté le badge 4, on le badge 7 gratuit ( ligne C=0 IN=1,4 OUT=7) et sinon, on peut l'acheter (C=1 IN=1,6 OUT=7), mais ce serait idiot.
Idem, pour la ville 8, on peut acheter le badge de la ville 8, mais on l'a gratos si on a acheté le badge 4
Donc après cette ville 8, soit on a tous les badges et on a payé 1, soit on a uniquement les badges (0,1,2,3,6) et on n'a rien dépensé.

Est-ce ok ? C'est bien conforme à ton problème ?
Et si oui, on a l'impression qu'on a un exponentiel qui augmente très peu.

Bonjour tbc92,

Effectivement, désolé, je suis allé trop vite, il y avait encore des bugs dans mon programme de génération de graphe. Voici donc les nouvelles données : Pièce jointe 661294
Le graphe pour N=6 a donc maintenant 8549 dépendances : 1465 avec un coût de 0 et 7084 avec un coût de 1.

Mais sinon, ta vision des choses est bien celle que j'imagine. Il s'agit donc bien de considérer un noeud comme acquis dès qu'on a les prérequis pour une de ses dépendances de coût 0. Ces dépendances de coût 0 n'amène donc pas de complexité dans les choix effectués.
Toute la question est donc quel choix de "progressions" de coût 1 effectuer pour bénéficier au maximum des "progressions" de coût 0.
Ces choix de coût 1 se font donc, après corrections des données, parmi 7084 possibilités. Et je précise que le "57" que j'avais évoqué est donc une borne supérieure, mais a également plus de 50% de chances d'être une borne inférieure, donc le minimum. Il s'agit justement de prouver que c'est le minimum, ou autrement de trouver un meilleur cas.
Donc pour trouver les bons 57 choix parmi les 7084, comme tu l'évoquais, il faudrait un moyen de ne pas tester et de favoriser les bonnes directions d'exploration (puisque 57 parmi 7084 = beaucoup trop). Tout en étant sûr de ne pas ignorer des choix qui auraient pu donner quelque chose.

Et sans rapport, juste histoire de mettre une illustration en plus, voici le graphe correspondant au cas N=2 (généré avec Graphviz, c'est déjà un peu le bazar, donc évidemment inutile de générer ça pour N >= 3).
Pièce jointe 661295
On peut trouver dans ce graphe une solution optimale qui nécessite seulement une dépendance de coût 1.

Pour le fichier graph_5, je trouve un cout de 26, quasi instantanément. Mais j'ai des doutes.
Pour le fichier graph_6, les temps explosent.
En fait, j'ai l'impression qu'on cherche à résoudre un problème qui n'est pas le problème original. A priori, il y a plein de symétries, et on doit pouvoir les exploiter pour réduire les recherches. Mais dans le fichier que tu partages, ces symétries ne sont plus visibles.

Bonjour tbc92,

Tu es vraiment sur la bonne voie, et je peux comprendre ta frustration pour ce qui est de "résoudre un problème qui n'est pas le problème original". Mais malheureusement, je ne peux pas me permettre de donner encore plus de contexte. En effet, il s'agit à l'origine d'un problème privé dont on essaie d'optimiser le coût. Et selon certains "a priori", on a supposé un certain coût optimal (mon fameux 57). Mais je me suis dis qu'on pouvait ramener ce problème précis à ce fameux graphe de dépendance, assez général, pour le résoudre de manière "brutale", sans "a priori".
Malheureusement, je n'ai pas trouvé d'algorithme qui me permettait de résoudre directement l'optimisation du graphe. S'agissant d'un problème que je pensais être "classique", j'ai posé ce problème général sur ce forum.
En l'occurrence, tu as tout à fait raison concernant les symétries : le graphe n'est qu'une accumulation de formules (raison pour laquelle j'ai dû "générer" le graphe) qui en toute logique amènent des patterns qui se répètent.

Et tu as également à 90% répondu à mon problème concret puisque le fameux 57 pour N=6 a été calculé selon une méthode, qui donnerai justement 26 pour le cas N=5. Donc à moins d'une forte coïncidence, il semble que notre méthode avec certains "a priori" soit tout de même bonne, même si on ne peut pas être sûr à 100%.

Merci encore pour toute ton implication, mais je pense donc qu'il vaut mieux s'arrêter là pour le cas concret.
Malgré tout, je souhaiterais laisser ce sujet ouvert dans la mesure où je l'ai créé également pour obtenir une réponse à la problématique générale de mon 1er post, qui pourrait m'être utile par la suite dans d'autres circonstances !

bonjour

votre graphe de dependance ne pourrais pas se resoudre par une matrice
Depart/arrive ou dans chaque case de couple connue on y indique le cout
ce qui normalement devrais nous donner les anteriorité et les precedent de facon plus precis

cela me rappel la methode perth par certains des aspects