Discussion :

[tomjr]

Bonjour,

Dans le cadre d'un projet, je dois coder (en java) une heuristique permettant de trouver le plus court chemin dans un graphe d'un point s à un point t sous deux contraintes:

1ere : Le chemin doit passer par k sommets minimum. (Nombre k imposé par le graphe)

2eme : Certains sommets du graphe font parti de sous-ensembles, passer par un des sommets appartenant à un sous-ensemble m'oblige à passer par tous les sommets du sous-ensemble.

J'hésite entre une modification de l'algorithme de Dijkstra ou une modification de l'algorithme de recherche en profondeur...

Qu'en pensez vous?

[tomjr]

S'il vous plaît, si quelqu'un a ne serait-ce qu'une vague idée de comment procéder je suis preneur, je bloque sur ces deux contraintes depuis un petit moment maintenant et je suis à court d'idées neuves...

Merci.

[pseudocode]

Tout dépend des données d'entrée : la taille du graphe, la densité de la matrice d'adjacence, le nombre de "sous-ensemble", ...

Les directions peuvent aller de l'exploration totale jusqu'aux algos génétiques...

[tomjr]

En fait, j'ai un "jeu" de 20 graphes. Tous ont 100 sommets et entre 3000 et 6000 arcs. Le nombre k est aux alentours de 50 (sachant qu'un simple Djkstra trouve la solution en 4 sommets) . Il y a souvent 3 sous-ensembles de 3 sommets chacun.

Avec une modification de l'algo de recherche en profondeur, je trouve des solutions respectant ma première contrainte pour seulement 9 des 20 graphes donnés.

Pour les 11 autres, une exception de type "StackOverflowError". J'utilise la récursivité mais ma condition d'arrêt doit être bonne puisqu'elle marche pour certains graphes...

[pseudocode]

En fait, j'ai un "jeu" de 20 graphes. Tous ont 100 sommets et entre 3000 et 6000 arcs. Le nombre k est aux alentours de 50 (sachant qu'un simple Djkstra trouve la solution en 4 sommets) . Il y a souvent 3 sous-ensembles de 3 sommets chacun.

Donc en gros 10% de chance de choisir un des sommets qui est dans un sous-ensemble. Ce n'est pas une probabilité très forte, on peut imaginer ne pas prendre en compte cette contrainte pour l'heuristique principale, mais seulement vérifier à la fin que la contrainte est respectée pour une solution.

Ce qui nous laisse trouver une heuristique pour la contrainte de passer par au moins "k" sommets, tout en minimisant la distance totale. Ce qui ressemble fort aux problèmes "CSP k-stops" que l'on rencontre dans les problèmes de routage sur les reseaux.

[tomjr]

10% de chances, pour le premier sommet choisi dans le chemin. Lorsqu'on arrive au 50eme sommet à choisir, on est à 25% non?

D'autant que j'ai l'impression que certains sommets de ces sous-ensembles ont été placés à des endroits "stratégiques" du graphe, avec donc une casi-obligation de les choisir...

J'essaye de repérer et de supprimer les sous-ensembles inutiles et de garder les sous-ensembles obligatoires car une suppression de tous les sous-ensemble me génère encore une "StackOverflowError"...

[pseudocode]

10% de chances, pour le premier sommet choisi dans le chemin. Lorsqu'on arrive au 50eme sommet à choisir, on est à 25% non?

oui, c'est sur que la probabilité augmente. Mais je trouve que cette contrainte reste assez faible comparée à la problématique du chemin le plus court à travers k sommets. Si on peut énumérer les chemins à k sommets, en commençant par les plus courts, le test de la 1ere contrainte est assez trivial.

As-tu regardé les algorithmes du CSP k-stops ?

[tomjr]

Je me suis largement inspiré d'un algorithme du CSP k-stops, celui-ci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Algorithm k-LDM(s, d)
// s and d are the source and destination, and path is the path constructed so far
1. Initialize path to s → d
2. For i = 1 to k
3. Find the point p in DB with the min distance from any line segment in path
4. Add p to path
5. Return path

Je créé le chemin de départ avec Dijkstra et j'ajoute à chaque tour le sommet de moindre coût.

Là, mon algorithme s'arrête dès que j'ai mes "k" sommets. Selon toi, je devrais continuer à ajouter des sommets au chemin jusqu'à ce qu'il n'y ai plus de sommets "hors chemin". Je sauvegarde tous mes chemins dont la longueur est supérieure à "k" dans une arrayList. Pour ma solution, je retourne le chemin qui respecte mes deux contraintes...

Je t'ai bien suivi?

En tous cas merci beaucoup pour ton aide, j'avance enfin...

[pseudocode]

Là, mon algorithme s'arrête dès que j'ai mes "k" sommets. Selon toi, je devrais continuer à ajouter des sommets au chemin jusqu'à ce qu'il n'y ai plus de sommets "hors chemin".

Il faut surtout regarder les chemins alternatifs de longueur "k". Par exemple on peut, pour chaque sommet du chemin actuel, prendre le "deuxième" sommet le plus proche (dans l'etape 3). Puis le "troisième", ....

Idem avec les chemins alternatifs de longueur k+1, k+2, ...

Au final, on se retrouve avec une liste de chemins, qu'on trie par longueur et dont on teste la contrainte #1.

Il reste à trouver un critère pour arreter de calculer et ajouter des nouveaux chemins dans la liste.

[tomjr]

Je suis resté sur l'idée de stocker un seul chemin par itération "k" et mon algorithme me donne enfin des chemins qui respectent les contraintes. Je suis loin du chemin optimal mais le temps me manque pour enchaîner sur ton idée de stockage des chemins alternatifs...

Encore merci pour ton aide!