> C'est un algo qui cherche des solution dans N^n à
Plutôt dans R+^n. Le simplex dans les entiers, c'est encore une autre paire de manches ...
> alors la taille de l'ensemble des soluces est expo : de taille 2^n
Non, en général, la solution est unique (c'est un sommet du polyedre). Ca peut aussi être une face du polyedre, et là, dans R, il y a une infinité de solutions.
C'est la complexité dans le pire cas de l'algo du simplex qui est exponentiel.
> Mais l'algo donne très rapidement un résultat et je crois qu'on ne sait pas encore pourquoi !?
En effet, en pratique, c'est très rare qu'on soit dans le cas exponentiel, donc le simplex marche bien en pratique. Là ou ca devient rigolo, c'est qu'il y a quelqu'un qui a trouvé un algorithme polynomial pour faire la même chose, mais qu'il n'est prèsque jamais utilisé parce que finalement, l'algo "exponentiel" va plus vite !
[^] # Re: simplexe
Posté par Matthieu Moy (site web personnel) . En réponse au message Complexité d'algorithmes. Évalué à 2.
Plutôt dans R+^n. Le simplex dans les entiers, c'est encore une autre paire de manches ...
> alors la taille de l'ensemble des soluces est expo : de taille 2^n
Non, en général, la solution est unique (c'est un sommet du polyedre). Ca peut aussi être une face du polyedre, et là, dans R, il y a une infinité de solutions.
C'est la complexité dans le pire cas de l'algo du simplex qui est exponentiel.
> Mais l'algo donne très rapidement un résultat et je crois qu'on ne sait pas encore pourquoi !?
En effet, en pratique, c'est très rare qu'on soit dans le cas exponentiel, donc le simplex marche bien en pratique. Là ou ca devient rigolo, c'est qu'il y a quelqu'un qui a trouvé un algorithme polynomial pour faire la même chose, mais qu'il n'est prèsque jamais utilisé parce que finalement, l'algo "exponentiel" va plus vite !