Trouver toutes les chaines distinctes entre deux points d'un graphe.

Bonjour! Je suis étudiant et je dois résoudre un problème en C.

On me donne un graphe, non orienté, non pondéré. Avec un sommet de départ 'x' et un sommet d'arrivé 'y' .

Le but est de trouver un maximum de chaîne (chemins) élémentaires entre x et y avec pour contrainte qu'il n'y ai aucun sommet commun à deux chaînes et que chacune des chaînes soit la plus courte possible... Suis-je clair? ^^

J'arrive à peu près à sortir une liste de toutes mes chaînes élémentaires entre x et y (avec une sorte de d'A* je pense ^^) mais je n'arrive pas à trouver une solution intelligente pour sélectionner parmi ces chaînes celles qui ne sont jamais en intersections..

Auriez vous des pistes de recherches? Avez vous besoin de plus d'info pour répondre?

Merci bien et merci!

Alors pour apporter quelques précisions et exemples:

Disons que j'ai le graphe suivant:

Sommets: Start, 1, 2, 3, 4, 5, 6, 7, End.

Arrêtes: Start-1, Start-2, 1-3, 1-4, 2-4, 2-5, 3-End, 4-End, 5-6, 6-7, 7-End

Pour trouver mes chemins, je pars de End avec un poids de 0 et j'incrémente mon poids dès que je m’éloigne. Chaque sommet possède un tableau de poids représentant leurs place dans les différents chemins.

Donc en terme de poids:

End : 0
3 : 1 et 1
4 : 1, 1, 3 et 5
7 : 1 et 1
6 : 2 et 2
5 : 3 et 3
2 : 2, 4, 4 et 4
1 : 2, 2, 2 et 6
Start : 3, 3, 3, 5, 5 et 7

A la fin je remonte mes poids décroissants en partant de Start, et je sauvegarde mes chemins.

Chemin 0: Start-1-3-End
Chemin 1: Start-1-4-End
Chemin 2: Start-1-4-2-5-6-7-End
Chemin 3: Start-2-4-End
Chemin 4: Start-2-4-1-3-End
Chemin 5: Start-2-5-6-7-End

Les chemins que je dois maintenant sélectionner sont Chemin 0 et chemin 3, car c'est l'ensemble des chemins les plus courts pour aller de Start à End sans intersections..

Donc dans cet exemple c'est plutôt triviale à voir, mais je n'arrive pas à imaginer l'algo..

Si vous avez besoin du code je peux le mettre, mais je ne pense pas que se soit vraiment nécessaire.. Au point où j'en suis j'ai un tableau de chaîne d'int, le tableau et chaque chaîne sont terminés par NULL.

Donc:

Code:

---

1 2 3 4 5 6 7 8 9

typedef struct s_list { int id; struct s_list *next; } t_list;   t_list *path[X]; path[X] = NULL;

---

Avec:

X = Nombre de chemins trouvé
et id = le numéro du sommet.


Voilà voilà... ^^

Bonjour,
comme un algorithme de type glouton ne convient pas (trouver le plus court chemin, recommencer avec le graphe privé de ce chemin, …), il faut, à mon avis créer un graphe des chemins C à partir de ton graphe originel G. Chaque nœud de C est un chemin dans G et deux nœuds de C sont reliés si les chemins qu'ils représentent dans G ont un nœud en commun. De plus tu affecte un poids à chaque nœud de C égale à la longueur du chemin dans G. Si on reprend ton exemple, ton graphe G originel peut être représenté ainsi :

Pièce jointe 190972

Du coup le graphe des chemins C est (suivant ton exemple) :
Pièce jointe 190973

Ton problème se résout en trouvant un stable de poids minimum dans C.
Les stables sont :
C0,C3 : P=4
C0,C5 : P=6
C1,C5 : P=6
C2 : P=6
C4 : P=4

Deux stables de poids minimum : C0,C3 et C4 tous deux de poids 4.

oO !!

C'est carrément ça!! MERCI @picodev !!!

Je comprends le raisonnement (comment tu fais) et je vois que ça marche :)

Par contre j'ai du mal à comprendre pourquoi ça marche ^^ . Et ce que représentent réellement ces stables.. En effet le Chemin 4 n'est pas du tout pertinent dans mon problème alors qu'il appairait comme étant autant pertinent que l'ensemble (Chemin 0, Chemin 3).

Encore une fois merci! Je vais pouvoir continuer mes recherches!

Citation:

---

Envoyé par sben42

[...]
Par contre j'ai du mal à comprendre pourquoi ça marche ^^ . Et ce que représentent réellement ces stables.. En effet le Chemin 4 n'est pas du tout pertinent dans mon problème alors qu'il appairait comme étant autant pertinent que l'ensemble (Chemin 0, Chemin 3).

---

Un stable est un ensemble de sommets deux à deux non adjacents, ce qui par construction du graphe C signifie un ensemble de chemin dans G n'ayant aucun sommet en commun : ce que tu cherches. Ensuite tout dépend des contraintes que tu vas utiliser pour discriminer les stables : somme des poids (ce que j'ai utilisé en exemple) ou encore nombre de chemins (à maximiser) suivi de somme des poids (à minimiser), …
La difficulté est dans le sens que tu donnes à «chacune des chaînes soit la plus courte possible» dans la phrase «un maximum de chaîne (chemins) élémentaires entre x et y avec pour contrainte qu'il n'y ai aucun sommet commun à deux chaînes et que chacune des chaînes soit la plus courte possible».

;) merci pour les précisions @picodev!

Je comprends mieux pourquoi le chemin 4 apparaît comme pertinent.

Pour l'ordre et l’importance des contraintes, ça va dépendre de mon état initial:

En fait je dois faire aller un nombre variable d'agent de mon sommet de départ à mon sommet d'arrivée.
Le tout en un minimum de déplacement.
Sachant qu'un agent ne peut se déplacer que de 1 en 1 (sommet) et qu'à part dans mes sommets de départ et d'arrivée, il ne peut y avoir qu'un agent à la fois sur un sommet.

Mon programme prend en paramètre le nombre d'agents, la liste des sommets et la liste des arêtes. (Etat Initial)

D'où mes contraintes "chemin le plus court" et "un maximum de chemin différent" qui va dépendre de mon nombre d'agents (s'il n'y en a qu'un il prendra forcément le plus court, mais s'il y en a plusieurs, il se peut que se soit plus pertinent d'avoir plus de chemins même s'ils sont plus longs que le chemin "unique" le plus court....)

Hum hum, pas très clair...

Par exemple si j'ai un stable S0 composer de C0 de poids 4 et un stables S1 composé de C1-C2-C3 de poids 15 (5 chacun).

Pour 1 agent, S0 est le plus pertinent;

Pour 2 agents, c'est égal de choisir S0 ou S1, sur S0 le deuxième agent devra attendre 1 tour avant de pouvoir emprunter le chemin. Qu'importe le stable choisi on mettra 5 tours;

Pour 3 agents et plus il faut choisir S1! Même si le premier n'arrive qu'au cinquième tour, ils arriveront 3 par 3. Ce sera donc plus rapide que de les faire tous patienter sur S0 ...

Je cherche, je code, et je reviens avec mes résultats ;) un grand merci!

Ok!

Alors, là où j'en suis:

Pour un graphe 'G' donné avec un nombre d'agent 'A' donné, j'ai la liste des stables 'S(i)' du graphe 'C' des chemins de 'a' vers 'b' dans le graphe 'G', avec 'a' et 'b' des sommets du graphe 'G'.

Tadadada! ^^

Je dois maintenant définir pour chaque stable combien de tour va être nécessaire pour faire traverser tout mes agents. (Avec comme contrainte: 1 seul agent sur un sommet autre que 'a' et 'b' et un déplacement d'1 sommet (maximum) par agent en 1 tour). Tout les agents démarre sur 'a'

Un stable est définit comme un ensemble de chemins ayant chacun un poids (nombre de sommet).
Donc disons que dans le graphe 'G' il y a,

- S(0) un stable de 1 chemin de poids (2)
- S(1) un stable de 2 chemins de poids (4 et 4)
- S(2) un stable de 2 chemins de poids (3 et 5)
- S(3) un stable de 3 chemins de poids (3, 3 et 8)

(On est d'accord, je suis pas sur qu'un graphe comme ça existe, mais supposons que oui, le graphe 'G' étant donné en paramètre...)
Je dois répartir A sur le stable le plus performant.

Donc ce que j'ai voulu faire c'est tester A sur chaque S(i) et choisir le plus petit nombre de tour 'y' nécessaire.

- 'y0' = S(0)('A')
- 'y1' = S(1)('A')
- 'y2' = S(2)('A')
- 'y3' = S(3)('A')

Donc dans notre exemple pour:

- A=1 ; y0=2, y1=4, y2=3, y3=3 ; y0 Win!
- A=2 ; y0=3, y1=4, y2=4, y3=3 ; y0=y3 Win!
- A=3 ; y0=4, y1=5, y2=4, y3=4 ; y0=y2=y3 Win!
- A=4 ; y0=5, y1=5, y2=5, y3=4 ; y3 Win!

On voit bien que selon 'A' le S(i) choisis va varier.
Et je n'arrive pas à écrire les fonctions (mathématiques) S(i) ... J'ai l'intuition qu'il y a un formule, mais je ne la trouve pas.

Pour les stables de type S(0), c'est simple: 'y' = 'P1' + ('A' - 1) // Avec P1 le poids du chemin du stable.
Pour les stables ayant plusieurs chemins, j'arrive à calculer une moyenne (approximative? ^^): yM = (SIGMA(Pi) + 'A' ) / i - 1 // Avec Pi le poids des chemins du stable, et i le nombre de chemin.
Je me rends bien compte, que 'y' n'est dépendant que du nombre de chemin (i) et des poids (Pi) ce ceux-ci! Donc il doit bien y avoir une fonction, une formule, qui me retourne ce 'y'.. Mais je ne trouve pas... ^^

Donc! Soit je me prends vraiment trop le choux pour rien!! ^^ Soit je touche presque au but et vos coups de pouce pourront me débloquer! Soit je rame.. Soit c'est pas possible et je dois vraiment faire un brut force sur chaque stable, sélectionner la meilleure répartition et la comparer aux meilleures des autres?

Si je suis pas au bon endroit ou si c'est trop indigeste, d'avance pardon. Et merci à ceux qui se pencheront sur mon problème :)