Plus court chemin dans un graphe avec contraintes

Question

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?

cs_tom123456789 · Answer

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.

sarahduweb · Answer

Bonjour, En cherchant qqch d'autre je suis tombée sur on pb, en fait qd j'étais à la fac j'ai fait un projet un peu identique mais en utilisant le système des fourmis. Le nom du sujet était les fourmis artificielles. En fait, si je m'en rappelle bien, on utilisait le système des fourmis, cad, que celles-ci dépose de phéromone pour se déplacer et donc on a utilisé cette idée - ci-*après une partie de l'introduction du rapport : Nous avons choisi de nous interesser plus particulierement a l'une de ces methodes, qui est celle des < fourmis articielles > ou < Ant-P-solveur >. Celle-ci est un solveur de contraintes, inspire du comportement collectif des fourmis. L'idee est de representer le probleme a resoudre sous la forme de la recherche d'un < meilleur > chemin dans un graphe. Des fourmis articielles circulent dans ce graphe de facon aleatoire et incomplete, a la recherche de < bons > chemins et communiquent entre elles en deposant sur les arcs du graphe une trace volatile, la < pheromone >. Alors si tu as tjrs besoin d'aide fait moi signe.

cs_tom123456789 · Answer

Merci pour ton aide mais j'ai résolu mon problème.

sarahduweb · Answer

ok, ben tant mieux, mais ça aurait été intéressant que tu y mettes ta solution pour qq1 d'autre car comme ça tu aideras qq1 qui comme toi sera ds ce même besoin, non ?

cs_tom123456789 · Answer

J'ai pas encore reçu ma note par contre!

Si j'ai une bonne note de projet, je partagerais ma solution, promis!

sarahduweb · Answer

ok, ben je croise les doigts pour toi : bon courage !

gelou72 · Answer

tom123456789, finalement, tu as eu une bonne note ? 

si tu as encore tes résultats, ça m'intéresserait d'avoir tes idées sur ton problème, vu que je suis dans le même cas, sans la deuxième contrainte !

Plus court chemin dans un graphe avec contraintes

7 réponses

Votre réponse

Discussions similaires