30

ha ok.
( valeur absolu c'est pas super linéaire mais bon si tu le dis ça doit marcher )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

31

Oui c'est pas linéaire, mais en explicitant x = abs(y) comme x>=y et x>=-y on s'en sort. Y a des trucs non-linéaires où tu peux feinter comme ça en ajoutant des variables avec des contraintes: abs, max, min, etc...

edit: et au fait, un programme linéaire en nombre entiers comme ça, ça fait déjà du branch&bound dans la babasse. Il fait des simplex avec la contrainte d'integrité relachée à chaque noeud. Ce que je voulais dire c'est qu'on pourrait lui montrer un algo branch&bound qui résoud directement son problème plutôt que le PLNE lui correspondant (vu qu'il a pas l'air d'être à l'aise en R.O.)
Tout ce qui passe pas par le port 80, c'est de la triche.

32

( tant qu'on a des trucs linéaires par morceaux on arrive à bricoler quoi ? -- tu m'excuses j'ai séché les cors de prog. linéaire)
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

33

oui ça doit être ça.
Tout ce qui passe pas par le port 80, c'est de la triche.

34

Euh, le linéaire par morceaux, c'est équivalent au linéaire mixed-integer, donc si tu penses te passer des contraintes d'intégralité des variables en introduisant des valeurs absolues, c'est mal parti, tu n'as pas simplifié le problème du tout.

À moins que tu ne puisses prouver P=NP, ce qui m'étonnerait gni, tout algorithme pour résoudre ce problème sera forcément exponentiel dans le pire des cas.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

35

Kevin Kofler (./34) :
donc si tu penses te passer des contraintes d'intégralité des variables en introduisant des valeurs absolues


non, c'est pas ça. ce que je dis c'est qu'on peut faire:

minimiser abs(x)
sous (contraintes)


en faisant:

minimiser e
sous (contraintes) ET e >= x ET e >= -x

Tout ce qui passe pas par le port 80, c'est de la triche.

36

Kevin Kofler (./34) :
À moins que tu ne puisses prouver P=NP, ce qui m'étonnerait gni.gif , tout algorithme pour résoudre ce problème sera forcément exponentiel dans le pire des cas.


Ben le simplex est exponentiel dans le pire des cas (en pratique je crois qu'il faut vraiment faire exprès ... )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

37

very > le simplex est polynomial

PL normal: simplex
PLNE : branch&bound avec des simplex à chaque noeud
Tout ce qui passe pas par le port 80, c'est de la triche.

38

non c'est exponentiel dans le pire des cas. (tu vois bien que notre problème là est NP-complet ... )

En pratique c'est souvent "rapide", s'too.
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

39

hmmm... en fait je pense qu'on peut pas généraliser ça à tout ce qui est linéaire par morceau, je pense qu'il faut aussi que la fonction soit convexe.

./38 > En fait, le simplex ne marche qu'avec des variables réeles, c'est un truc qui se balade de sommet en sommet dans le polyèdre explicité par les contraintes.
Et dans notre cas c'est pas le simplex qui résoud, c'est un truc plus global qui lance le simplex plein de fois: il fait un branch&bound. Donc dans le pire des cas, il fera 2^n calculs oui, mais le simplex en soit est polynomial.
Tout ce qui passe pas par le port 80, c'est de la triche.

40

Ha ça doit être l'habitude d'utiliser simplement 'simplex' pour le méta-simplex cheeky

Sinon pour la convexité j'y ait pensé aussi, en fait je crois qu'il faut que la fonction délimite une partie convexe du plan (au dessus ou en dessous), donc qu'elle soit soit convexe, soit concave, mais pas un peu des deux. (par ce que bon à un - près ça revient au même )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

41

onur> l'algo du simplexe n'est pas polynomial (mais il y a des algos polynomiaux pour la PL à variables réelles)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

42

Méthodes de points intérieurs. smile
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

43

ok, je crois que me souvenir que simplex est polynomial mais que c'est pas démontré, c'est ca?
Tout ce qui passe pas par le port 80, c'est de la triche.

44

Non, pour un système dégénéré, le simplex est démontré être exponentiel.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

45

En fait y a pas un unique algo mais une famille d'algos ; les plus courants sont exponentiels, et on ne sait pas s'il y en a des polynomiaux, c'est peut-être à ça que pensait Onur.

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

46

Pollux > ça a l'air plus détaillé en français ( http://fr.wikipedia.org/wiki/Problème_du_sac_à_dos )
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

47

En fait, cest pas tout à fait le knapsack, si?
dans le sac à dos, on maximise la valeur du sac, là il veut minimiser sa distance à N.
Tout ce qui passe pas par le port 80, c'est de la triche.

48

ah oui pardon j'ai lu ./1 un peu trop vite... ("s'approcher uniquement par additions" m'avait évoqué "suite croissante" et donc inférieure à N)

tu peux quand même l'encoder dans deux instances du pb du sac à dos (un pour les solutions <=N et un pour les >=N) donc c'est fondamentalement la même chose, mais bien sûr si tu prends un algo genre programmation dynamique c'est plus simple de l'étendre au pb de ./1 sans le couper en deux ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

49

On est d'accord.
Tout ce qui passe pas par le port 80, c'est de la triche.

50

Je n'ai pas lu vos pages. L'algo auquel je pense trouverait la solution en (N-1)+(N-2)+...+(N-(N-1)) tests. Ca fait bien N(N-1)/2 opérations ?
On a bien un truc grosso-modo exponentiel.

Sur une liste de 10 nombres, on aurait besoin de 45 opérations. Les algos que vous proposez font mieux ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

51

oui ca fait qlqchose comme N(N-1)/2, mais c'est pas tellement exponentiel ^^

52

ça fait N(N–1)/2 oui, donc c'est pas du tout exponentiel (N n'est pas en exposant confus), c'est quadratique, mais c'est louche, aussi trioui
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

53

Thibaut, sont-ce des paires de nombres que tu essaies d'additionner là? Pour résoudre le problème, il faut aussi prendre en considération les sommes de plus de deux nombres!
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

54

Oui oui.

Jyaif : Ca s'approche de N². C'est pas ça un algo exponentiel ? On appelle ça un algo quadratique ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

55

n^2 est un algo quadratique.
2^n est un algo exponentiel.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

56

oui exponentiel ça veut dire que N est en exposant.
Quadratique veut dire que N est au carré, cubique qu'il est au cube, polynomial que la complexité est de l'ordre d'un polynôme en N (ce qui revient en fait à être O(N^k) pour un certain k, les autres puissances n'étant pas significatives)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

57

Moi je pense à un truc comme ça:

On trie le tableau d'entrée par ordre décroissant (n log(n)) jusque là on est bon.
On déclare deux variables où on met:
meilleurSol == la meilleure solution trouvée (c'est une liste qui est un sous-ensemble de la liste de début)
meilleurSolVal == la valeur de cette solution (la somme des nombres qu'il y a dedans)


f(i) {
si (i> tableauDuDebut.length) return;
On regarde l'élément n° i, est-ce que son ajout à meilleurSol donne une meilleure solution? (est-on plus proche de N?)
Si oui, on dit meilleurSol = meilleurSol + {premier élément}, et appelle f(i+1)
si non, return;
}

au début, on appelle f(0)
... un truc du genre.
Tout ce qui passe pas par le port 80, c'est de la triche.

58

Bon, le fait de mettre dans l'ordre décroissant ne sert à rien, je pensais encore au cas où on ne doit pas dépasser N et éliminer la solution et la suite du tableau à partir de l'indice i+1, si jamais ca dépassait N.

Mais bon, grosso modo l'idée est là, je pense que tu peux t'en sortir avec un truc comme ça.
Tout ce qui passe pas par le port 80, c'est de la triche.

59

On ne fait pas un parcours linéaire du tableau dans ce cas ? Autrement dit, on ne testerait que N solutions parmi N(N-1)/2
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

60

si, il manque qq chose en effet (jy pensais sous la douche là wink)

il faut pas appeler seulement f(i+1), mais aussi f(i+2), f(i+3)... jusqu'à f(tableauDeDepart.length)

edit: bon cest pas bien au point encore.
Tout ce qui passe pas par le port 80, c'est de la triche.