Déduire une formule à partir d'un graphe

[As2piK]

Bonjour à tous,

Dans le cadre de nos cours de Théorie de la Complexité, nous avons du réaliser un programme calculant une tournée pour le problème du voyageur de commerce en appliquant les heuristiques aléatoires et du plus proche voisin, afin de calculer la complexité des l'heuristiques.

Voici le résultat de mes mesures :



Comme vous pouvez le constater, mes droites sont plutôt droite, mais sur un graphe à échelles logarithmiques, et là est mon problème : je n'ai AUCUNE idée de se à quoi peut ressembler la formule de ces courbes.

Puis-je vous demander un peu d'aide ?

Merci

[Dlzlogic]

Bonjour,
C'est très probablement de la forme y = A x^B
Donnez-moi vos valeurs et je pourrai le confirmer, et bien sûr vous dire comment on le calcule.

[As2piK]

Merci pour la réponse.

Voici mes valeurs. Désolé pour le format, elles sont formatées pour être utilisées sur GNUplot

Code: Tout sélectionner

#Mesures pour le voyageur de commerce pour N villes dans une grille unitaire
#N      Random duration      Rand2opt duration   PPV duration   PPV2Opt duration
10      0.0               2.560181887240565   0.0            0.0
50      0.0               6.596479338504248   0.0            0.0
100      0.00312002         8.787887725987579   0.0            0.001
500      0.0               19.127785589068587   0.001312002      0.02808018
1000   0.0               27.223871411013384   0.00624004      0.1404009
5000   0.0               60.3130763359414   0.21528138      4.09034622
10000   0.0               84.95945202804786   0.85488548      16.77946756
50000   0.00312002         189.20288785469535   21.34405682      490.75106582
75000   0.0               231.21673400302743   47.9079071      1326.95698608

Merci

[Dlzlogic]

J'ai pas très bien compris toutes vos données, la valeurs avec 0.00000 sont inexploitables, vous vérifierez. A l'impression seules deux décimales apparaissent, mais les valeurs sont bien lues.

Code: Tout sélectionner

N° 1  x=19.13 y=0.00
N° 2  x=27.22 y=0.01
N° 3  x=60.31 y=0.22
N° 4  x=84.96 y=0.85
N° 5  x=189.20 y=21.34
N° 6  x=231.22 y=47.91
Ajustement puissance  Y=A * X puiss(B)       nbpts= 6  A = 0.00000  B = 4.21  R2 = 0.999 (emq=1.994)


Là c'est avec la seconde série de durées

Code: Tout sélectionner

N° 1  x=19.13 y=0.03
N° 2  x=27.22 y=0.14
N° 3  x=60.31 y=4.09
N° 4  x=84.96 y=16.78
N° 5  x=189.20 y=490.75
N° 6  x=231.22 y=1326.96
Ajustement puissance  Y=A * X puiss(B)       nbpts= 6  A = 0.00000  B = 4.28  R2 = 1.000 (emq=40.273)



[Judoboy]

Je comprends pas trop le problème, t'as tes valeurs, là tu les as tracées en logarithmique mais tu peux pas refaire la courbe avec une échelle linéaire ?

[As2piK]

Bonjour,

Merci beaucoup pour vos réponses. Je vais regarder cet après-midi les résultats :)

Judoboy non, enfaite les valeurs viennent de mes mesures sur le programme réalisé, en secondes. Il était demandé de réaliser les graphes sur des échelles logarithmiques. Se que je ne sais pas faire, c'est faire se qui s'appelle je crois une "Régression linéaire" afin de déduire l'équation, sur cette échelle.

Merci encore ;)

[Dlzlogic]

Bonjour,

Merci beaucoup pour vos réponses. Je vais regarder cet après-midi les résultats

Judoboy non, enfaite les valeurs viennent de mes mesures sur le programme réalisé, en secondes. Il était demandé de réaliser les graphes sur des échelles logarithmiques. Se que je ne sais pas faire, c'est faire se qui s'appelle je crois une "Régression linéaire" afin de déduire l'équation, sur cette échelle.

Merci encore

Je vous ai répondu que c'était une fonction puissance, puis je vous ai envoyé la vérification de mon affirmation. En d'autres termes, je ne vous ai rien dit ou expliqué, juste mis sur la piste.
Posez-vous donc la question : comment deviner sans faire de calcul que c'est une fonction puissance (je tiens à préciser que je ne suis ni mystique, ni devin) :lol3: