Bonjour,
j'aimerai savoir si il existe un algorithme de complexité au plus O(n^3), qui pour deux points donnés sur un graphe complet, trouve le chemin qui minimise la plus longue arrête (et donne la longueur de cette arrête au passage).
On connait les coordonnées de tous les sommets.
J'ai en fait trouvé un tel algorithme, mais en O(n^4), et j'aimerai trouver plus rapide.
Merci d'avance...
Je ne suis pas sûr de bien comprendre, qu'entendez-vous par minimiser un maximum ?Envoyé par totode
Bonjour,
j'aimerai savoir si il existe un algorithme de complexité au plus O(n^3), qui pour deux points donnés sur un graphe complet, trouve le chemin qui minimise la plus longue arrête (et donne la longueur de cette arrête au passage).
On connait les coordonnées de tous les sommets.
J'ai en fait trouvé un tel algorithme, mais en O(n^4), et j'aimerai trouver plus rapide.
Merci d'avance...
Vous voulez trouver le plus court chemin ? Ou le plus long ?
Et d'ailleurs, pour compléter, je me rend compte que je ne vois pas très bien en quoi consiste la tâche à effectuer.
Je résume donc, pour voir si nous nous comprenons bien :
Nous avons un "graphe", qui est en fait un tableau composé de coordonnées, donc un tableau contenant les doublets de valeurs par exemple x,y.
Ensuite, on passe à l'évaluation.
Nous prenons alors "un point", donc un élément du tableau, puis un autre, au hasard ou pas.
Et à partir de ces deux éléments du tableau, nous voulons trouver les autres coordonnées (éléments du tableau), éventuelles, situées sur le plus court chemin reliant les deux coordonnées initiales.
Si vous pourriez préciser si ça correspond à ce que vous voudriez faire,
Merci.
Salut,
avec un tableau t de n-1 éléments initialisés par t[i] est la distance entre A (le sommet de départ) et i un sommet du graphe.
une fonction foo prend t en argument et renvoi t' un tableau
foo(t) => le tableau t' avec t'[i] minimise le maximum entre (t[j],a(j,i)) ou j parcours le tableau
en rappelant la fonction foo n fois foo(foo(foo...(t))) le min du tableau fourni la valeur souhaité. Pour connaître le chemin associé il faudra stocker dans une variable annexe la valeur de j qui minimise le maximum entre (t[j],a(j,i)).
on appelle foo n fois, on parcours le i puis les j soit O(n^3).
Bon je vais préciser un petit peu ma pensée...
Le but ce n'est pas de trouver un parcours plus court ou plus long (peu importe la taille du parcours d'ailleurs) entre deux points.
Pour imager un petit peu, on veut aller d'un point A a un point B, en faisant des pauses (les sommets traversés), et le but est de trouver le chemin qui minimise la plus grande distance sans faire de pause...
Je ne suis pas sur de comprendre ce que fait votre fonction...
foo(t):
var aux=infini
for i de 1 a n-1:
for j de 1 a n-1:
if max(t[j],a(j,i))<aux:
aux=max(t[j],a(j,i))
fin de j
t'[i]=aux
fin de i
return t'
D'accord, j'ai compris, je pense que ça va marcher super!
En fait mon algorithme en O(n^4) était quasiment le même, sauf que je ne sais pas pourquoi j'essayais tous les sommets de départ, et du coup j'avais toutes les distances, mais une complexité mauvaise...
Re : Algorithme sur graphe complet
En fait crois qu'il va me falloir finalement du O(n^2) c'est encore trop lent
Désolé mais je ne comprend pas tout.
Ca c'est bon.
Avec "pause" (ce que je comprend comme, "en passant par des points intermédiaires") ou "sans pause" (aller de A en B sans passer par des points intermédiaires) ????
Et que veut dire "minimiser la plus grande distance" ???
En fait, pour chaque chemin, on calcule la plus longue arrete, et parmi toutes les valeurs possibles de ces arretes, on veut la plus petite, par exemple, avec:
A=(0;0)
B=(4;0)
C=(-1;3)
D=(2;4)
E=(5;3)
Le meilleur chemin de A à B est ACDEB et il a une plus longue arrete de longueur, ce qui est optimal...
Suis-je clair
Les poids des arcs sont il les distances?
Oui, et votre premier algorithme était bon, mais malheureusement il me faut plus rapide...
Tu t'es demandé si ça existe ?
Re : Algorithme sur graphe complet
Eh bien il y a n^2 distance, donc a priori si on les parcours seulement une fois ca doit etre envisageable, non?
C'est un peu plus compliqué que ça parce que le nombre de chemins est un peu plus élevé.
Mais tu peux partir de ça et voir si ça convient à ton cas:
https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm
peux tu spécifier la taille du problème. Et montrer ton code.
Je crois que je dois pouvoir adapté à mon cas, je vais essayer mais je pense etre sur la bonne voie
En fait mon problème est à la base plus compliqué, du coup cela ne consiste qu'en une partie du code... Mais sinon cette partie du code en python ressemble à ca:
(les variables depart,nbdepart,sommet et nbsommet sont connues à l'avance)Code:d=[10**10]*nbsommets for loop in range(nbsommets): d[loop]=[0]*nbsommets for loop1 in range(nbsommets): for loop2 in range(nbsommets): d[loop1][loop2]=distance(sommet[loop1][0],sommet[loop1][1],sommet[loop2][0],sommet[loop2][1]) transformations=1 while transformations==1: transformations=0 for a in range(nbdeparts): for b in range(nbsommets): for c in range(nbsommets): if d[depart[a][0]][b]>max(d[depart[a][0]][c],d[c][b]): d[depart[a][0]][b]=max(d[depart[a][0]][c],d[c][b]) transformations=1 if d[depart[a][1]][b]>max(d[depart[a][1]][c],d[c][b]): d[depart[a][1]][b]=max(d[depart[a][1]][c],d[c][b]) transformations=1
