? probleme np

[amine801]

salut
existe-il un algorithme efficace pour calculer le chemin élémentaire
le plus long dans un graph orienté moi j’ai beau cherche je n’arrive pas a trouver de solution
je crois que c’est un problème np complet

[amine801]

hello all
vu que j'ai pas recu de reponse je me permet de relancer

[maturin]

tu prends E0 ton point de départ (c'est l'ensemble des points à distance 0)

tu considères En l'ensemble des points à distance n
tu prends En+1 l'image de En par toutes les relations que tu as auquel tu otes tout les points de E0 U E1 U ... U En, c'est l'ensemble des points à distance n+1

tu t'arrêtes quand tu es passé par tous les points tu as ton chemin maxi pour n maxi tel que En non vide.

Tu passeras au maxi 1 fois par chaque sommet et tu feras au maxi N calculs avec N ton nombre d'arcs.

[amine801]

ce que tu me propose la c'est une sorte de femeture transitive
(sauf condition d'aret )
qui ne conduit pas forcement au chemin maximale

[maturin]

ben c'est à partir d'un sommet donné.
S'il y a d'autre sommet qui ne sont pas atteint il faut refaire le meme algorithme sur les autres sommets.

[amine801]

ton algo calcule en fete autrement dit
tout les chemins dordre n ainsi avec juste quelque
modifiction il pourait donnes la longeur du chemin elmentaire
maximale mais on aucun cas il peut fournir les somets
qui compose ce chemin

[maturin]

ok je commence à comprendre la question :hum:

donc pour reprendre mon algorithme.
Tu fais la meme chose sauf que pour chaque point image de En+1 tu notes son antécédant de En. Et s'il a plusieurs antécédant t'en prends un au hasard.

Donc à partir d'un sommet donné tu es capable de trouver le chemin le plus long.

tu recommences à partir des autres sommets qui ne sont éventuelement pas atteints.

[maturin]

enfin ça ça te donne un des chemins les plus longs tu les a pas tous. Sinon il faut stocker tous les antécédants pour chaque point.

[amine801]

je crois que ca marche pas (lol)
ou sinom je vois pas tres bien ce que tu veux dire
tu peu ecrire l'algo sous une forme plus formel

[amine801]

on peut represente le graph par une matrice A
si i->j exist
sinom

[amine801]

et donc la version original de ton algo reviendre a faire
un produit matriciel a l'ordre n

le produit sur les entier est fait en modulo 2

[maturin]

bon je tente une dernière explication, pour moi ca me semble marcher mais bon j'ai ptetre encore raté un truc.

Je note (x,a,o,d) le point Sx d'antécédant Sa à distance d du point So
Et je note E(o,d) l'ensemble des points à distance d du point So

1 - CONSTRUCTION DE E(o,n)
tu as E(o,0) qui est composé de l'unique point (0,null,o,0)

pour tous les points (i,j,o,n) de E(o,n) je regarde toutes les images du sommet Si (c'est à dire tous les Sk tels que Aik=1 avec ta notation)

si il existe déjà un point de E(o,0) U ... U E(o,n) tel que x=k je ne le garde pas
sinon j'ajoute (k,i,o,n+1) dans E(o,n+1)

Quand tu trouves E(o,n+1) vide tu arrêtes cela arrivera pour un rang noté N(o)

2 - GENERALISATION A L'ENSEMBLE DES SOMMETS
Si tu regardes F(o)=E(o,0) U E(o,1) U ... U E(o,N(o))
Ca te donne l'ensemble des sommets (en regardant les coordonnées x) qui sont atteignables depuis So, avec leur distances à ce point So.

si il existe un sommet Si qui n'appartient pas à F(o) (c'est à dire qu'aucun point de F(o) n'a pour coordonnées x=i)

tu recommences l'algorithme à partir de ce point pour construire F(k)

Quand tu auras passé cet algorithme suffisamment de fois tous tes sommets appartiendront à au moins un des ensembles F(k).

3 - CHEMIN LE PLUS LONG
Il te suffira de ne retenir que le F(k) qui as le N(k) le plus grand.
Et pour trouver ton chemin tu prends un point de E(k,N(k))
Tu recherches son antécédant dans E(k,N(k)-1)
etc...
Quand tu arrives à E(k,0) tu arrêtes (c'est ton point So)
Ca te donne ton chemin en sens inverse.

[amine801]

pour tous les points (i,j,o,n) de E(o,n) je regarde toutes les images du sommet Si (c'est à dire tous les Sk tels que Aik=1 avec ta notation)

si il existe déjà un point de E(o,0) U ... U E(o,n) tel que x=k je ne le garde pas
sinon j'ajoute (k,i,o,n+1) dans E(o,n+1)

Quand tu trouves E(o,n+1) vide tu arrêtes cela arrivera pour un rang noté N(o)

Le choix est déterminé par l’indicage des point
ce qui crée un problème car si on marque un point
celui la ne peut plus servir pour obtenir un chemin même si son utilisation est plus judicieuse après
dans un état avance du parcourt des sommet
je sais si je me fait bien comprendre j’aurais voulus afficher une image d’un graph qui mets en échecs
l’algorithme mais je sais pas comment faire

[amine801]

voici l'image du graph
http://www.hiboox.com/image.php?img=892838c3.png