Calcul de coût - Page 1

Bon.. je vous passe du sujet mais pour la petite histoire l'algo concerne la recherche de la plus courte tournée bitonique .
Je ne sais pas s'il y a une relation avec le tri bitonique, mais si quelqu'un le sait il peut me le dire

Ma question concerne l'exactitude de mon calcul du cout.
J'ai l'algo suivant:

(en C-like)

long_min(a,r){
    int i=max(a,r)+1;
    if (i>=tailleTab) return;
    return min(long_min(i,r)+dist(P[a],P[i]),
               long_min(a,i)+dist(P[i],P[r]));
}

Pour le cout, je dis
T(n) = T(n-1) + 4*(n-1)
(à un cas particulier près de n=1 peut etre...)

Ce qui donne un coùt en O(n²).

Cela vous semble juste?

euh j'ai peut-être mal compris ton truc, mais ton algo m'a plutôt l'air d'être en O(2^n)... la fonction avec n=tailleTab appelle deux fois la fonction avec n-1, chacune appelant 2x avec n-2, etc ^^
et en fait tu recalcules bcp trop de choses, puisque tu as seulement O(n^2) entrées possibles, donc si tu rajoutais un simple cache ton algo passerait en O(n^2)...

Pour plus de clarté sur ma formule T(n) = T(n-1) + 4*(n-1), voici comment j'ai raisonné:
En augmentant la taille du tableau, tailleTab ( =n), un par un, on voit l'ajout du nombre d'appel:



désolé pour la qualité des images... :s





le nombre d'appel en plus semble etre 4*(n-1)

pollux > Oui c'est un exercice où ils demandent d'abord l'algo "naïf", puis il faut trouver sans calculs redondants puis une solution itérative. Mais justement, d'habitude la solution naïve est plutôt exponentiel et là, je trouve polynomiale. C'est pour ca que ça m'a semblé curieux, je me trompe quelque part?

./3> euh, mais justement, ce serait le cas si tu faisais un caching, mais là tu rappelles la fonction à chaque fois : donc en fait sur ton graphe ça correspondrait à des arêtes supplémentaires pour chaque noeud qui a plus d'une arête entrante -- si tu dessines le graphe pour n=4, tu devras dupliquer toutes les arêtes partant de (2,3) et de (3,2) ^^

EUh... je ne vois pas

pour n=4, j'aurai les arcs:
(3,0) --> (4,0)
(3,1) --> (4,1)
(3,2) --> (4,2)

(0,3) --> (0,4)
(1,3) --> (1,4)
(2,3) --> (2,4)

mais aussi:

(3,0) --> (4,3)
(3,1) --> (4,3)
(3,2) --> (4,3)
et
(0,3) --> (3,4)
(1,3) --> (3,4)
(2,3) --> (3,4)

ce qui fait 12.
Mais là, sans "caching" ni rien, le graph correspond

bien à tous les appels de l'implémentation naive de cet

algorithme. Y compris meme les appels redondants, non?
Quand j'appel avec a=0 et r=0, on voit exactement quels

cas sont appelés plusieurs fois et ces cas sont bien

comptabilisés.

mais tu as deux arêtes entrantes pour (3,2), ce qui veut dire que f(3,2) est appelée deux fois : donc quand f(3,2) va appeler f(4,2), ça fera deux appels au total, et il faut donc que tu aies deux arêtes dans ton graphe de (3,2) vers (4,2) donc au total ça te ferait 16 = 2^4 arcs au lieu de 12...

Ok très bien j'ai compris
Mais comment je peux formuler ca mathématiquement? Il suffira pas que j'écrive "ca a une tete d'exponentielle"

ben c'est simple, déjà la complexité ne dépend que de i=max(a,r)+1 [puisque tu peux écrire max(i,r) et max(a,i) seulement en fonction de i], après ça c'est direct si tu réécris la complexité ^^

#include <stdio.h>


int tailleTab;
int nbAppel;

int main(){
	printf("Bienvenue\n");
	tailleTab=5;
	nbAppel=0;
	long_min(0,0);
	for (tailleTab=0;tailleTab<30;tailleTab++){
		nbAppel=0;
		long_min(0,0);
		printf("Pour tailleTab=%i on a %i appels\n",tailleTab,nbAppel);
	}
}

int min(int a,int b){
	if (a<b) return a;
	return b;
}
int max(int a,int b){
	if (a>b) return a;
	return b;
}

float long_min(a,r){
    int i=max(a,r)+1;
    if (i>=tailleTab) return 0;
    //printf("long_min(%i,%i)\n",a,r);
	nbAppel++;
    return min(long_min(i,r),
               long_min(a,i));
}

donne:

C:\Documents and Settings\Onur\Bureau\tournée bitonique>tournee.exe
Bienvenue
Pour tailleTab=0 on a 0 appels
Pour tailleTab=1 on a 0 appels
Pour tailleTab=2 on a 1 appels
Pour tailleTab=3 on a 3 appels
Pour tailleTab=4 on a 7 appels
Pour tailleTab=5 on a 15 appels
Pour tailleTab=6 on a 31 appels
Pour tailleTab=7 on a 63 appels
Pour tailleTab=8 on a 127 appels
Pour tailleTab=9 on a 255 appels
Pour tailleTab=10 on a 511 appels
Pour tailleTab=11 on a 1023 appels
Pour tailleTab=12 on a 2047 appels
Pour tailleTab=13 on a 4095 appels
Pour tailleTab=14 on a 8191 appels
Pour tailleTab=15 on a 16383 appels
Pour tailleTab=16 on a 32767 appels
Pour tailleTab=17 on a 65535 appels
Pour tailleTab=18 on a 131071 appels
Pour tailleTab=19 on a 262143 appels
Pour tailleTab=20 on a 524287 appels
Pour tailleTab=21 on a 1048575 appels
Pour tailleTab=22 on a 2097151 appels
Pour tailleTab=23 on a 4194303 appels
Pour tailleTab=24 on a 8388607 appels
Pour tailleTab=25 on a 16777215 appels
Pour tailleTab=26 on a 33554431 appels
Pour tailleTab=27 on a 67108863 appels

oui, et ?

et c'est tout.

merci

Manifestement 2^(n-1) - 1, d'après les chiffres à l'exécution.
Si tu réécris la complexité à partir de ce qu'a indiqué Pollux, ça donne quoi ?

Oui j'ai raisonné avec ce qu'il a dit sur le post ./2

L'appel de taille n appel deux fois avec la taille n-1 qui eux mêmes appellent deux fois avec la taille n-2 etc..

                T(n)
         /              \
     T(n-1)           T(n-1)
    /    \           /      \
T(n-2) T(n-2)    T(n-2)   T(n-2)

Le nombre d'éléments d'un arbre binaire complet de hauteur n est de l'ordre de 2^n.
Donc le compte est bon.

Heu, au risque de paraitre ignare, c'est quoi comme "algo" ? et ce genre de truc sert a résoudre quoi ?

apparemment http://www.cs.sunysb.edu/~algorith/lectures-good/node14.html décrit la tournée bitonique, mais si c'est ce qu'onur veut implémenter il faut corriger :
if (i>=tailleTab) return;
en
if (i>=tailleTab) return dist(P[a],P[r]);

et pour ce qui est de la relation avec le tri bitonique, je pense pas qu'il y en ait, à part que le terme "bitonique" désigne le fait qu'on colorie en 2 couleurs... (en l'occurrence, les "points du haut" et les "points du bas")

Oui il est facile de voir que je n'ai pas implementé _exactement_ l'algorithme, j'ai viré tout ce qui est calcul en temps constant lorsque j'ai codé le test.
L'algo de départ, je trouve (cf ./post0)

long_min(a,r){ 
    int i=max(a,r)+1; 
    if (i>=tailleTab) return; 
    return min(long_min(i,r)+dist(P[a],P[i]), 
               long_min(a,i)+dist(P[i],P[r])); 
}